Timeline for Can an algorithm decide whether a program computes all strings?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2014 at 14:45 | comment | added | Joel David Hamkins | Also "interleaving"... | |
| Nov 17, 2014 at 13:48 | comment | added | Joel David Hamkins | The term "interweaving" is also used. One interweaves infinitely many processes into one. | |
| Nov 16, 2014 at 22:36 | comment | added | usul | Dovetailing is a more general term for interleaving any series of computations. Your question is a special case of dovetailing. But dovetailing does not imply that you run the machine indefinitely, or which computations it is that you're interleaving, so it is not by itself a term for the procedure you mention. Just wanted to be sure that's clear. | |
| Nov 16, 2014 at 19:27 | comment | added | Benedict Eastaugh | @JimHefferon plenty of them, e.g. chapter 5 of Rebecca Weber's recent book Computability Theory. More classically, it's used in Hartley Rogers's 1967 book Theory of Recursive Functions and Effective Computability. Google Books should give you page references in both cases. | |
| Nov 16, 2014 at 18:45 | comment | added | Jim Hefferon | @BenedictEastaugh Do you happen to have a reference? I've heard it called time slicing but I can't think of a place where I've seen that term used in print. | |
| Nov 16, 2014 at 17:43 | comment | added | Benedict Eastaugh | @usul "This a standard trick -- running all TMs in parallel -- but I don't know if it has a name." This is called dovetailing. | |
| Nov 16, 2014 at 17:40 | comment | added | usul | @JoelDavidHamkins, you're right, I removed the statement about Rice's theorem. | |
| Nov 16, 2014 at 17:40 | history | edited | usul | CC BY-SA 3.0 |
removed reference to rice's theorem
|
| Nov 16, 2014 at 13:41 | comment | added | Joel David Hamkins | That is, Rice's theorem applies when one is separating programs by a criterion that is invariant if two programs compute the same function or accept/reject the same inputs. But my sense is that the OP's concept of UTP is not invariant in this sense, since I don't think he'll count as a UTP any program that never halt. Rather, he is interested in the ones that perform that universal task of simulating all programs. | |
| Nov 16, 2014 at 12:58 | comment | added | Joel David Hamkins | I don't think Rice's theorem applies directly here, since the algorithm he describes is not a decision algorithm, and indeed, it never halts on any input. | |
| Nov 16, 2014 at 11:49 | history | answered | usul | CC BY-SA 3.0 |