Home » forums » LtU Forum

The Halting Problem on Turing Machines

I'm no longer convinced that the Halting Problem on Turing Machines is undecidable. The caveat is that it depends on the hyper-pedantic semantics of what it means to "halt" and whether or not a directed graph can be used to accurately capture the semantics of a Turing Machine, specifically the state transitions table. There is no requirement that the directed graph be acyclic.

Assuming that an informal, slightly ambiguous description of the state transition table is plausible and acceptable, then "halting" would be defined as "one of the designated states that cause the Turing Machine to halt is reachable from the start state". Fairly simple analysis that does not consider the machines input in any way should then be able to determine whether such a machine 1) "trivially" always halts, 2) "trivially" always loops, or 3) "may halt or loop depending on the input".

We're obviously interested only in case #3. Then question becomes: "Assume that the input to the machine is defined" (i.e., we are considering a specific, exact case). To be clear, no additional input will be provided, the tape head is at the "start" position of the input, and the machine is in the q_0 start state, ready to begin execution. Everything about the machine at this point is fixed and finite with the sole exception that to left and right of the input the tape contains an infinite number of "blank" symbols.

It is my understanding, which may be very wrong, is that the "Halting Problem" states that given such a machine, it is impossible to rule out case #3. To be clear, "impossible" in this sense means genuinely impossible, not the "practically impossible" due to the astronomically large combinatorial explosion of finite permutations.

After a lot of careful consideration, I've come to the conclusion that it is actually "practically impossible" and not "genuinely impossible". If it really is "practically impossible", then I assert that it is possible, at least in principle, to always solve the "halting problem" given a specific machine and input pair.

The key insight I used to reach this conclusion was the following: Each state transition moves the tape head exactly one position, either to the left or right. Assume that all the states move the tape head to either the left or right. If this is the case, then there can be at most |Q| tape positions before we must "loop" back to the start, aka our current state. This allows you to consider each state as some kind of modulo |Q|.

If you permit me some "informal, slightly ambiguous latitude", I hope you can see that it is possible to incorporate tape mutations in to the above along with "left / right" direction changes. That is to say, at a relative position of 0, there is some finite subset/powerset expansion of symbols, left / right transitions, and mutations that is bounded by some finite number, probably |Q|. Since this is "informal", I have yet to work out the specific details, only that at this point in the analysis, it seems plausible. Then, for each state in Q, it should be possible to "trace" its evolution through all of those paths, recording which states are associated with which symbols. This is the "viable paths" set for each state in Q, and the paths that were not reached are obviously discarded.

Once that's done, and with the help of a bit of "symbolic hand waving", you can begin to "cross join" these viable paths among states with the input that is present on the tape. This should take ~ O(n) steps, where n = the number of tape squares that is input (i.e., not 'blank') and may require "subset/powerset expansion" of virgin viable paths to be associated with each tape square of input (again, this is informal, not fully worked out).

Assuming this whole contraption holds together, you can then begin some form of graph substitution, reduction, and minimization. Hypothetically, this should allow you to determine whether or not a "terminating state" is reachable from the start state without having to "run" the turing machine to completion. In ultra simplified terms, it is almost a form of "regular expressions" for turing machine state transitions. Because each state can be shown to be reducible to some modulo |Q|, it should (hopefully!) be possible to treat this intermediate representation as some form of giant "chinese remainder theorem" of simultaneous congruences where the goal is to see if a "terminating state" can be reached. The specific details of how this is going to be done is a bit ambiguous even to me, but it does seem to rest in that "it might be possible" realm. That is to say it shifts the problem domain from one that is "essentially impossible" to one that is at least tractable.

Again, highly informal at this point. Does the above seem plausible, or did I make a terrible mistake somewhere? What problems do you see with the above? Are the problems "death blows", or "practical implementation issues" / "description is a bit vague on how to handle this particular corner case which might be a serious problem"? Reduction to an actual implementation always turns up its own set of problems, but can anyone see any reason why an attempt shouldn't be made? Also, can anyone point me to some "graph reachability of states for Turing Machines" analysis papers?

Thanks for your help.

By johne at 2010-09-21 00:15 | LtU Forum | previous forum topic | next forum topic | other blogs | 7750 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Modus Tollens

First, if P implies Q, but Q is false, it's usually wise to re-examine P. :)

Second, this statement is false:

If you permit me some "informal, slightly ambiguous latitude", I hope you can see that it is possible to incorporate tape mutations in to the above along with "left / right" direction changes. That is to say, at a relative position of 0, there is some finite subset/powerset expansion of symbols, left / right transitions, and mutations that is bounded by some finite number, probably |Q|.

The set of tape-strings over any non-empty alphabet is infinite. So you can't do what you're saying here.

By Sam Tobin-Hochstadt at Tue, 2010-09-21 00:48 |

Bounded tape string

Sorry, apparently this particular point wasn't clear. What you say is true, and I'm not denying it, I'm specifically bounding the tape string to be considered to a length of |Q|. In other words, at a relative position of zero, enumerate all the possible permutations of the symbols, left/right movements, all permutations of tape mutation and potential symbols under the "current" tape position, etc. This forms a (very large) tree of all possible permutations, where the depth of the tree is |Q|.

Then for each state q in Q, place it at the root of the tree. The root will contain |{Γ, b}| root nodes, where Γ = the symbols set, and b is "blank". Then, "walk each root node forward" until you hit the bottom of the tree, keeping the visited nodes (along with what state visited them), and discarding the rest. This is what allows you to efficiently stitch together all the possible finite permutations that each state is capable of "reaching and/or generating". The process of stitching the whole thing back together is still a bit vague, but basically I'm hoping that the stitching process can be shown to be reducible to solving a system of simultaneous congruences, and therefore efficiently solvable with an appeal to CRT.

If what you are saying is "provably true", then I guess I'm looking for that paper that shows when the states, symbols, and tape "input" are finite it is the addition of "an infinite number of blank symbols to the left and right of the tape input" that "provably" (in the strongest sense of the word) shows that there must be an infinite path through the states in such a way that it can not, not even in principle, be shown to have a "periodic loop".

In a round about way, I'm now leaning towards a view that a TM with a fixed, finite input can be shown to do one of two things: 1) have a finitely periodic loop (i.e., Mersenne Twister), or 2) halt. The nature of TM's makes it extremely difficult to analyze them, but technically not impossible. The tape may be infinite, but there can only be a finite "distance" between two states which can contain only a finite number of possible permutations, and the infinite number of squares to the left and right of the input are guaranteed to be b. This can be used to "relativize" and simplify the analysis without getting caught up in the quagmire of "infinite tape length".

At least, that's my hope. :)

And just in case we're "crossing signals", I'm not saying the above is possible for "all possible permutations of input", but the analysis is applicable only to a specific, fixed, bounded input. That is to say, "Does the TM halt with this specific input?" I do not see how to (easily) extend my idea to the general case of "Is the TM guaranteed to halt with all possible input?"

By johne at Tue, 2010-09-21 03:14 |

This is off-topic, but I'll

This is off-topic, but I'll bite. You're viewing a TM with fixed input as basically a very large finite state machine. It is not. A TM can use its infinite tape to, e.g. implement an arbitrary sequence of transitions through its states that is not periodic. E.g. even the simplest TM that implements a counter N can stay in state X (or region of states X) for N steps, then transitions to state Y and stays there for N+1 steps, then transitions back to state X and stays for N+2 times, etc, will never exhibit periodic behavior. A TM could use any number of counters to achieve arbitrarily complex behavior. Because the tape is infinite, the counters can count up without bound.

As mentioned below, however, the details of states and tapes of TMs have nothing to do with undecidability. The fact that a TM is powerful enough to allow a construction of a universal TM is enough to prove the halting problem undecidable.

By Ben L. Titzer at Tue, 2010-09-21 23:36 |

Sorry to disappoint, but you're wrong, off-topic,

and the Wikipedia page is actually very clear and informative:

http://en.wikipedia.org/wiki/Halting_problem

Don't think of the Halting problem in terms of the low-level turing machines. Think of a machine with a "HALT" subroutine, and then using this subroutine to decide whether some carefully-crafted programs which call themselves call HALT will halt or loop. The important notions are not in the low-level tape details: it's that a turing machine can in a sense describe itself completely. And so can some strings in the lambda calculus, and anything that is turing complete, and why the halting problem exists (and is undecidable) in all of these representations.

By thinking at this low level, you 1) run the risk of a bug seeping into the case-by-case stuff or the "informal" parts, and more importantly 2) ignore that the Halting problem is absolutely prevalent in all sorts of places, and not only for the particular universal machine you're thinking of.

By Carlos Scheidegger at Tue, 2010-09-21 03:32 |

This is off-topic for LtU.

This is off-topic for LtU. I am closing off comments.

By Ehud Lamm at Tue, 2010-09-21 03:42 |