Say I have the Universal Turing Machine encoding of a specific Turing machine T. Also say I have the encoding of a specific input s. Is the question of whether T halts on s decidable? Can simulating running T on s be used to reach an answer?
Asked
Active
Viewed 416 times
1
-
Sounds like the Halting Problem to me. – yinnonsanders Jul 28 '17 at 01:59
-
I'm voting to close this question as off-topic because it is about the theory of computing, not programming. – Raymond Chen Jul 28 '17 at 02:19
-
Possible duplicate of [What exactly is the halting problem?](https://stackoverflow.com/questions/1111155/what-exactly-is-the-halting-problem) – Welbog Jul 31 '17 at 13:32
1 Answers
0
This problem is decidable in all instances. Any specific, fixed TM either halts or doesn't on any specific, fixed input, assuming for the moment that the excluded middle is not something you want to challenge here. For a specific instance of your problem where you are fixing the TM and input, the TM should either halt-accept for all inputs (not the specific, fixed input with which you are parameterizing the problem, but the typical input to the TM which will solve our parameterized problem) if that specific instance if the problem has a TM halting on the supplied input, or it should halt-reject if that specific instance has a TM that fails to halt.
The difficulty is that for any specific instance of the problem, we know that the specific TM either halts or doesn't given the specific input, but we don't have any computationally effective way to know which is the case. Certainly one or the other is (again, whether you accept the excluded middle is a larger discussion) and therefore the specific instance of the problem is decidable - regular, even - but that doesn't help us too much, except to understand computability a little better.
Note that there are lots of instances of this problem where we could know which of the two cases holds; for instance, it is not hard to produce TMs which halt, or fail to halt, on any or all inputs. Those instances of the problem are not only decidable and regular, but we know which decidable/regular languages they are.
Patrick87
- 27,682
- 3
- 38
- 73
-
"Any specific, fixed TM either halts or doesn't on any specific, fixed input," Yes, thats true. Exactly what the halting problem asks - which is proven to be undecidable (but semi-decidable). – BassSultan Jan 04 '20 at 19:24
-
@BassSultan Not quite. Be careful here. The halting problem has as its domain the set of all pairs of TM encodings and all input tapes. OP's question has as its domain one specific pair. OP's problem is always solved by one of the following two TMs: (1) do nothing and halt-accept; (2) do nothing and halt-reject. It's the problem of knowing which of these two TMs correctly solves the problem which is undecideable; that's the halting problem. – Patrick87 Jan 05 '20 at 13:06
-
-
@BassSultan No, not at all. If a specific TM looped forever, a TM which halt-rejects would solve OP's problem. If it halted on the input, a TM which halt-accepts would solve OP's problem. We don't need to simulate the specific TM on the specific input. We know either it halts or it doesn't, so one of the two TMs would work. If you had two guesses each trial, you would be right 100% of the time. Whether or not a language is decidable or not has nothing to do with whether we actually know how to decide it. – Patrick87 Jan 05 '20 at 20:27
-
i think i am missing some crucial information regarding the terminology used here. what do you mean by a "specific, fixed TM"? – BassSultan Jan 06 '20 at 13:39
-
@BassSultan By specific, fixed TM, I mean that the problem scope is restricted from the set of all TM representations to one single TM representation. By a specific, fixed input, I mean that the problem scope is restricted from the set of all input tapes to one single input tape. The problem of deciding the halting problem for the specific, fixed pair of TM and input is decidable because we can design a Turing machine which (a) halt-accepts if the specific TM halts on the specific input (b) halt-rejects if the specific TM doesn't halt on the specific input and (c) does ... – Patrick87 Jan 06 '20 at 14:22
-
anything at all for all other inputs (maybe it loops forever, maybe it accepts, maybe it rejects... whatever). We don't know whether the TM needs to halt-accept or halt-reject but we know it must do one of the two and for that reasons one such TM is guaranteed to correctly decide our specific instance. This extends to the same problem for any finite set of TMs and inputs. Only in the infinite case can this method not work since our TMs must have finitely many states; if you infinitely many states then the halting problem is decidable. – Patrick87 Jan 06 '20 at 14:24