Timeline for What do we know about restricted versions of the halting problem
Current License: CC BY-SA 2.5
36 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Nov 10, 2010 at 19:43 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 301 characters in body; edited tags; added 1 characters in body
|
| Nov 10, 2010 at 19:30 | vote | accept | Mohammad Alaggan | ||
| Nov 10, 2010 at 8:53 | comment | added | Kaveh | Possibly related questions: is there a complexity theory analogue of rices theorem in computability theory?, MO: completeness easiest hardest problems. | |
| Nov 10, 2010 at 3:12 | comment | added | Tsuyoshi Ito | My criticism still applies. I know what a homomorphism means in the standard sense, but you are speaking of a configuration being homomorphic to another configuration without referring to the whole configuration graphs. But I am not sure if it matters. Anyway I do not think that I can answer anything that pleases you (primarily because I do not know much). | |
| Nov 10, 2010 at 2:47 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 300 characters in body
|
| Nov 10, 2010 at 2:38 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 478 characters in body
|
| Nov 10, 2010 at 2:37 | comment | added | Mohammad Alaggan | A TM A is homomorphic to TM B if the transition graph of A is homomorphic to that of B, in the standard sense of homomorphisms of graphs with labeled nodes AND edges. A transition graph (V,E) of a TM is such that V=states, E=transition arcs between states, labeled with the symbol read off the tape and the symbol written to it, and the direction the head show move to. | |
| Nov 10, 2010 at 2:14 | comment | added | Tsuyoshi Ito | I read the your “definition” of “non-self-referencing”. I cannot call it a definition because you have not defined what it means for a configuration of one Turing machine to be “homomorphic” to a configuration of another Turing machine. Usually, a homomorphism is defined as a mapping between the set of configurations of one machine to the set of configurations of another machine, and you cannot speak of a homomorphism between two configurations alone. I doubt that there is any way to define “non-self-referencing Turing machines” while keeping the halting problem still nontrivial. | |
| Nov 10, 2010 at 0:50 | comment | added | András Salamon | Some of the discussion at cstheory.stackexchange.com/questions/2823/… seems relevant to your question. | |
| Nov 9, 2010 at 23:26 | comment | added | Mohammad Alaggan | It's a nice idea. But, yes as you said, it is also may be called by "merging" its states with the current machine, so that the new machine has the machine it calls "coded into" its state transition table. This why I said "homomorphic". | |
| Nov 9, 2010 at 23:15 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 32 characters in body
|
| Nov 9, 2010 at 23:05 | comment | added | user1338 | I missed pointing out that the only way, under my version, to call a machine would be via the UTM. So, basically I was discussing a model of computation under which every machine is more or less prohibited from ever calling itself. That said, it may still be possible to call the machine by writing a similar program. | |
| Nov 9, 2010 at 22:59 | comment | added | Mohammad Alaggan | @Philip: The problem is that the machine to be tested for halting, doesn't necessarily get executed. Only its discription will be analysed. In this case, it might be buried deep in the discription, and on several recursive levels as well, it might not be always possible to compute if a given description will eventually call itself. However in the exposition above we are not considering the computability of this property, but taking it for granted and reasoning about the resulting sets. | |
| Nov 9, 2010 at 22:10 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 359 characters in body
|
| Nov 9, 2010 at 20:54 | comment | added | user1338 | Would it make sense to phrase this question by requiring a hypothetical UTM that simulates Turing machines on inputs to automatically reject any machine that attempts execution on itself? E.g., if I ran UTM(100010101010111100,100010101010111100), that would instantly reject without simulating the computation. | |
| Nov 9, 2010 at 20:50 | comment | added | user1338 | @turkistany, I think I read that Boolos proposed a proof of Godel's Incompleteness theorem that relies on the Berry paradox and does not use diagonalization. I would imagine there are similar proofs for the halting problem; perhaps Chaitin's proof regarding Kolmogorov complexity could be adapted for this purpose. | |
| Nov 9, 2010 at 20:25 | answer | added | Mark Reitblatt | timeline score: 9 | |
| Nov 9, 2010 at 19:01 | history | edited | Mohammad Alaggan | CC BY-SA 2.5 |
added 902 characters in body; added 56 characters in body
|
| Nov 9, 2010 at 18:51 | comment | added | Mohammad Alaggan | @Matt Groff: turkistany is not speaking of any machine $Q$, he is speaking about $Q$ which decides the halting problem on the set $S$ of non-self-referencing turing machines. If $Q$ always halts, that means that the halding problem for $S$ is decidable. | |
| Nov 9, 2010 at 18:41 | comment | added | Matt Groff | What is the significance of always-halting Turing machine $Q$? What problems does this present? | |
| Nov 9, 2010 at 17:39 | comment | added | Mohammad Al-Turkistany | A diagonalization proof relies on deriving a contradiction which leads to the conclusion that TM $Q$ does not exist. If you disallow self-reference then there is no contradiction and you can't exclude the existence of $Q$. | |
| Nov 9, 2010 at 17:25 | comment | added | Mohammad Alaggan | @turkistany: I am not sure I got what you mean, can you elaborate more ? | |
| Nov 9, 2010 at 17:21 | comment | added | Mohammad Al-Turkistany | @M. Alaggan, If we disallow self-reference, then we can't exclude the existence of always-halting Turing machine $Q$. | |
| Nov 9, 2010 at 17:12 | comment | added | Mohammad Alaggan | @turkistany: The proof provided in the background (in the question), I don't think it depends on the diagonalization method, or am I wrong ? | |
| Nov 9, 2010 at 17:01 | comment | added | Mohammad Alaggan | @Rob Simmons: Invoking $Q$ on $S$ is denoted by a Turing machine $Q$ with a set of states and a certain possible initial inputs on the tape (corresponding to any member of $S$), with the head initially at the beginning of that input. A machine $W$ invoking $Q$ on $S$ "indirectly" means that there is a (finite) sequence of steps that $W$ would take to make its configuration "homomorphic" to the initial configuration of $Q(S)$. | |
| Nov 9, 2010 at 16:52 | comment | added | Mohammad Al-Turkistany | This raises an interesting question: Are all uncomputability (undecidability) proofs traceable to Cantor's diagonalization method? Is there any undecidability proof that does not rely directly or indirectly on the diagonalization method? | |
| Nov 9, 2010 at 16:51 | comment | added | Rob Simmons | @M. Alaggan. Now I'd want a definition of "invokes $Q$ on $S$ indirectly," which I suspect to be as difficult to define as the original "self-reference" :) | |
| Nov 9, 2010 at 16:42 | history | edited | Mohammad Al-Turkistany | CC BY-SA 2.5 |
edited body; edited tags
|
| Nov 9, 2010 at 16:33 | comment | added | Mohammad Al-Turkistany | Wouldn't that break the diagonalization method used to prove the undecidability of the Halting problem? | |
| Nov 9, 2010 at 16:29 | answer | added | Rob Simmons | timeline score: 11 | |
| Nov 9, 2010 at 16:21 | comment | added | Mohammad Alaggan | @Tsuyoshi: Thanks for the information, and the link. I am actually more interested on the theoretical results of which classes are known to be halting-decidable (I am not talking either on proving a particular algorithm). The programming language motivation is my colleague's, not mine. | |
| Nov 9, 2010 at 16:17 | comment | added | Tsuyoshi Ito | There are studies of provably halting programs (this class does not include all halting programs, though). Basically they are a pair of a program and a proof that it halts. For example, if I am not mistaken, Agda only allows programs which halt. I think that people working on logic and programming languages have more to say on this. | |
| Nov 9, 2010 at 16:05 | comment | added | Mohammad Alaggan | Indeed it would be tricky. The goal is to define it as the set that does not lead to the contradiction posed in the proof. I would try a shot: assuming that there is a Turing machine $Q$ that decides the halting problem for a set of Turing machine $S$, then $S$ is non-self-referencing with respect to $Q$ if it excludes all machines that invokes $Q$ on $S$ (directly or indirectly). Does that sound plausible enough ? | |
| Nov 9, 2010 at 15:53 | comment | added | Sam Nead | "the remaining set of non-self-referencing" Before I can sensibly discuss this set, I'd like a definition of "self-reference". However, I think that will be a tricky thing to define? | |
| Nov 9, 2010 at 15:14 | history | asked | Mohammad Alaggan | CC BY-SA 2.5 |