Constructing a non-halting turing machine

1.4k Views Asked by At

I'm wondering if constructing a non-halting turing machine is as simple as I think it is. It seems like all that's required is one loop.

Is the flow-chart machine attached accurately non-halting? Basically, you pass over all marks in the alphabet (moving in some arbitrary direction) and then switch states whenever you get to a blank, so that you just keep switching back and forth in a blank stretch of tape. This seems like it wouldn't halt but I fear I'm critically misunderstanding something. enter image description here

2

There are 2 best solutions below

2
On

As mentioned in the comments, this seems to be a perfectly reasonable description of a non-halting Turing Machine. Do you have a particular reason to think that the description of a non-halting Turing Machine would be complicated?

One reason people tend to think that non-halting Turing Machines would be complicated is due to the halting problem, but that's a fundamental misunderstanding. Figuring out if a particular TM halts is often quite easy: any TM that computes addition, or multiplication, or any other total function clearly halts on every input. The difficulty arises when you try to determine the set of all halting TMs.

4
On

Your example is quite right, and shows that it is often easy to tell if a Turing machine will halt or not. However, it is not always easy to do so.

For example, here is a piece of pseudocode that - with work - can be turned into a Turing machine (which ignores its input):

  • At stage $n$, we look at the odd number $2n+3$.

  • We search through the primes below $n$ until we find two, $p, q$, which sum to $2n+3$ (note that this is a finite search - there are at most $(2n+3)^2$-such pairs, and in fact vastly fewer than that).

  • If we find such, we move on to stage $n+1$; otherwise, we halt.

This Turing machine halts if and only if the Goldbach conjecture is false. Indeed, there are lots of problems in mathematics which can be "coded" into the halting/non-halting question of a specific Turing machine on a specific input. For instance, all questions of the form "Do [axioms] imply [statement]?" can be so coded (although I'm being a bit vague here, and it takes some work to make this precise).

There are also questions in math which can't be so coded, or which we don't currently know how to code in this way; for instance, the twin prime conjecture may be one of these. Such statements, however, can often be coded as questions about Turing machines in other ways. E.g., while TPC is not (obviously) equivalent to a sentence of the form "This machine halts on this input," it is easily equivalent to the statement "$M$ halts on all inputs" for some TM $M$.


Hopefully, the above explains how - while building examples of Turing machines with specific properties is often easy - telling whether an arbitrary Turing machine has a specific property is generally very hard (and indeed this can be made precise, and proved, as Rice's theorem).