Lambda the Ultimate

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.