Timeline for Can an algorithm decide whether a program computes all strings? [closed]
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2014 at 9:23 | vote | accept | Ward Blondé | ||
| Nov 19, 2014 at 9:21 | comment | added | Ward Blondé | @JoelDavidHamkins Would it be possible to remove the comments that were addressed to previous versions of the question? It is my ambition to get this question upvoted to at least neutral again :-) I guess UTP is now precisely defined. | |
| Nov 18, 2014 at 21:17 | review | Reopen votes | |||
| Nov 19, 2014 at 10:36 | |||||
| Nov 18, 2014 at 21:11 | comment | added | Ward Blondé | I have brought the question back to its essence, leaving away all traces of the idea of a 'program that computes all programs'. Computing all strings appears to be more precise. | |
| Nov 18, 2014 at 21:01 | history | edited | Ward Blondé | CC BY-SA 3.0 |
Reduced the question back to its essence, removing all traces of the concept 'program that computes all programs'
|
| Nov 18, 2014 at 0:05 | history | closed |
Henry Cohn Stefan Kohl♦ Ryan Budney Ricardo Andrade Ramiro de la Vega |
Needs details or clarity | |
| Nov 17, 2014 at 17:13 | history | edited | Ward Blondé | CC BY-SA 3.0 |
Added the alphabet of the program.
|
| Nov 17, 2014 at 13:03 | history | edited | Ward Blondé | CC BY-SA 3.0 |
deleted 146 characters in body
|
| Nov 17, 2014 at 5:12 | review | Close votes | |||
| Nov 18, 2014 at 0:05 | |||||
| Nov 17, 2014 at 1:16 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Nov 16, 2014 at 22:10 | comment | added | Joel David Hamkins | For example, in the alphabet of the usual decimal digits, I could design a machine that simply wrote out the numbers 0123456789101112131415... and so on, and every finite string of digits would eventually appear, so we could find there any kind of representation of simulated computation, but I wouldn't say that this machine is actually simulating any of these computations. | |
| Nov 16, 2014 at 21:40 | comment | added | Joel David Hamkins | I'm sorry to say that I don't find it to be precise. Do the programs have inputs? What is the alphabet? You talk about a "largest non-interrupted" region, but I don't see how there could be a "largest" such region, if finite, unless you mean "largest" with respect to some other unstated criterion. Do you count any program that systematically writes every finite string on the tape to be a UTP? If so, then simulating the computations seems to have nothing to do with it, and you are just talking about a program whose tapes are universal in that sense. (I think this is a necessary condition.) | |
| Nov 16, 2014 at 17:46 | history | edited | Ward Blondé | CC BY-SA 3.0 |
added 535 characters in body
|
| Nov 16, 2014 at 15:12 | comment | added | Joel David Hamkins | That isn't the problem. The problem is that you are asking if a certain set is decidable, but you haven't really told us exactly what the set is. The answer to your question depends on this, since if the answer to "is $p$ a UTP?" depends only on syntactic things about how $p$ is designed to work, then it will be decidable; but if the answer depends on the behavior of $p$ as it proceeds, then it will not. | |
| Nov 16, 2014 at 14:00 | history | edited | Ward Blondé | CC BY-SA 3.0 |
Added the relation between computing a program and being a UTP. Added an addedum about irrational numbers.
|
| Nov 16, 2014 at 13:44 | comment | added | Joel David Hamkins | Your edit gives a more precise example of a UTP, but what I was asking for was: what counts as a UTP exactly? | |
| Nov 16, 2014 at 13:40 | history | edited | Ward Blondé | CC BY-SA 3.0 |
Added a more formal definition of UTP in a new paragraph.
|
| Nov 16, 2014 at 12:56 | comment | added | Joel David Hamkins | ...with the behavior of the machine and whether externally we can view it as undertaking the UTP idea, then the kind of counterexample you propose would be a counterexample. So more precision in the question is needed in order to answer. | |
| Nov 16, 2014 at 12:54 | comment | added | Joel David Hamkins | Your definition of what it means to be a UTP is not sufficiently precise to answer the question. If what it means to be a UTP is that the algorithm performs a certain precisely specified kind of algorithm (with no extra checks or other computation), then yes, this will be decidable, since we can inspect the code to see if it carries things out exactly like that. (The algorithm in your proposed counterexample does not follow the UTP template, since it also checks to see if a certain program halts, and then does something else.) But if your definition of what it means to be a UTP has to do... | |
| Nov 16, 2014 at 11:49 | answer | added | usul | timeline score: 1 | |
| Nov 16, 2014 at 10:50 | history | asked | Ward Blondé | CC BY-SA 3.0 |