A short description of Turing machines and a halting problem undecidability proof

[CraigD]

The halting problem, has provokes some acrimonious debate in threads such as 17098, 18973 and 19237.

 

Before considering this famous and significant problem, I think it’s a good idea to understand what a Turing machine is. Though much explained in textbooks and websites, I’d like in this thread to try stating clearly and precisely what a Turing machine is, and outline the halting problem and Turing’s famous proof of its undecidability.

 

A Turing machine M consists of:

• An alphabet – a list of characters that are allowed to occupy cells of a tape. The alphabet can be a subset of a common character set, such as the ASCII characters used in this post, or can be larger, but must be finite. The tape, however, is infinite – an innate quality of Turing machines, which are idealization of, not actual physical computing machines, is that they can never “run out” of tape.
  
• A state diagram (which can be drawn graphically, or written as a table) that, given the following:
  
  • Old State – the current state
    
  • Old Tape – the alphabet character at the current “read/write head” position on the tape
    

  specifies the following:

  • New State – the next state
    
  • New Tape – the alphabet character to place on the tape at head position
    
  • Move – how to move the tape:
    
    • R to move 1 position to the right
      
    • L to move it 1 position to the left
      
    • 0 to not move it.

Turing machines run in discrete machine cycles, in which the machines state is changed to New State, the head position tape cell is set to New Tape, and the tape is moved according to Move.

 

There are two special states:

• START – the state the machine begins in
  
• STOP – the state that indicates the machine has halted (by some conventions, the state table must specify that for all nodes with CUR=STOP, NEXT=STOP for all IN
  

An initial tape D is specified by:

• The sequence of alphabet characters to the left of the head
  
• The sequence of characters at and to the right of the head
  

By some conventions, a single or two characters at all positions to the left and right of the specified sequence may be specified, and/or only the left or right initial sequence is allowed.

 

For an example of a state diagram table and initial tape see post #33 of “Halting Undecidability proof faulty?”. Rather than naming its start state START, it names it 0, a difference merely in naming convention. It uses the shorthand of an Old Tape of “else” to specify a collection of rows with every character not previously specified for a given Old State, and a blank New Tape to specify New Tape=Old Tape – per the simple definition above, these would have to be expanded so that are no “elses” or blanks.

 

Note that a tape character sequence can describe a state diagram, via many schemes - for example, using an alphabet of the characters appearing in the table in post #33, one additional character as a delimiter “,” between table columns, and, for convenience, a special character “/”to indicate the end of the table. An initial tape can be follow it, with the special character marking the end of its two sequences. So, post #33’s table and tape could be:

0,a,a,R, 10,1,a,a,R,11, … ,53,d,1,R,1//a0111b1110110011c/

“//” appears because there’s no sequence to the left of the head.

 

Once the reader has a firm grasp of what a Turing machine is – to assure this, it’s helpful to complete a few exercises in writing state diagram tables to perform various simple functions on the tape, such as arithmetic operations, which is easiest with the aid of a Turing machine simulator computer program with which to try them – she/he’s well prepared to consider the halting problem.

 

Turings famous proof consists of 3 main steps:

• Assume that a Turing machine H – a “halting deciding program”, or just “halting program” for short – exists that, given an tape representing the state diagram M and the starting tape D, sets the head cell of its tape to the character HALTS if M with D reaches its state STOP, “LOOPS if it doesn’t, then reaches its state STOP.
  
• Create another machine K, by
  
  • changing the state table row with Old State=START with one with Old State=ORIGINALSTART
    
  • replacing the START row with a machine that makes copies the tape D (ie: creates tape D//D/), then, when done, reaches state ORIGINALSTART
    
  • replacing the rows in the table with New State=STOP and New Tape=Halts with rows with New State=LOOP, and adding a rows with Old State and New State=LOOP, Old Tape=each character, and New Tape and Move=anything.

  [*]Consider the head cell’s character of H when it reaches state STOP given a tape consisting of K’s state table as both the M and D part’s of H’s tape (ie: K//K/):

  • If H ends with HALTS, then K – which, remember, contains H and some extra state table rows at its beginning and end – reaches and stays in state LOOP.
    
  • If H ends with LOOPS, then K reaches state STOP
    

  Either case is a contradictions. Because H, by definition, must work on any machine and tape, even one like that’s a modified and duplicated version of itself, it is shown that H can’t meet the conditions of its own definition, so cannot exist as assumed.

Note that we don’t need to attempt to actually write H, just assume that it exists. Because, as we’ve defined a Turing machine, we know that H must have a START and STOP state, so we know we can construct K as described above, producing the contradiction on which this proof depends.

 

Thought it’s not necessary to know – and accepting the consequences of proofs of its impossibility, impossible to know – the details of how H is actually written, it can be helpful to consider how “weak” versions of H capable of determining is limited kinds of M and D halts or not. Like most explorations of computing, this covers a vast territory of which I’ll just touch a couple points.

 

If M and D have been written in a careful way that assures that only a finite number of tape cells will be used, it is effectively a finite state machine F. One can write a “weak” halting program W for any finite state machine by writing a program that executes (or “runs”) it, creating a list of every one of F’s states. If this results in M’s STOP state being reached, W stops with HALTS. If W lists the same state of F twice, it stops with LOOPS. Because there are a finite number of states that can be listed, it’s guaranteed that, if it doesn’t stop with HALTS first, it will eventually list the same state twice, and stop with LOOPS – though as F can easily have a huge number of states, this can take an impractical number of machine cycles. The halting problem, though, is one of theoretical principle, not practical implementation, so this is OK.

 

If M and D haven’t been written to make them effectively a finite state machine, the approach of writing H to run M and D isn’t guaranteed to succeed, however, this isn’t an argument against the possibility of a halting program, because there are other approaches to writing H, such as analyzing it without running. I give an example of such a program in the next post.

 

Because any given K showing that a given H candidate H? is not a halting program, it’s tempting to think that a sort of “super H” program that recognizes when a K effectively contains it could be a successful halting program. However, note that the proof outlined above doesn’t make any assumptions about H?, other than that it has a START state, and 2 STOP states, one with head cell HALTS, the other with LOOPS, to which the simple alterations described can be made. So for every H? that is “immune” to some collection of Ks, a K that it’s not immune to can be made. Because, unlike its tape, a Turing machine must have a finite state diagram, no H? can every be large enough to recognize and be immune to every possible K, so no successful “universal” H can exist.

[CraigD]

The Brain**** esoteric computer language is discussed in the thread [thread=]“Brain****”[/thread]. In this post, I’ll describe a variation of this language I call “Lobotomized Brain****”, and give a halting deciding program for it.

 

Lobotomized Brain**** (LBF) is Brain**** with only the characters +, [, and ]. Thus, it has only a single 1-byte cell, which is assumed to overflow without error, that is, incrementing the value 255 results in a value of 0. It can be interpreted on any Brain**** interpreter that has this overflow behavior.

 

A halting deciding program for LBF is described by the following vague pseudo-code logical expression:

If, for each [...] in program P

( if (count of + before [...]) =mod 256= 0

or (count of + before [...]) =mod (count of + within [...])= 256

) and (count of + withing ]...]) == 0

, program P halts.

 

The following MUMPS code implements this program:

[noparse]n (XLLBFHP,R) s P=R,I=1 f  s J=$f(P,"[",I) x XLLBFHP(3) q:'R!'J  x XLLBFHP(1) q:'I  e  x XLLBFHP(2) q:'R!'I  ;XLLBFHP: Lobotomized Brain**** halting program
s E=$e(P,I,J-2),L1=$l(E)-$l($tr(E,"+")) i '(L1#256) s D=1 f I=J:1 s E=$e(P,I),D=$s(E="[":1,E="]":-1,1:0)+D s:E="" (I,R)="" q:'I  i 'D s I=I+1 q  ;XLLBFHP(1): if (count of + before [...]) =mod 256= 0
s I=$f(P,"]",J),E=$e(P,J,I-2),L2=$l(E)-$l($tr(E,"+")) i $s(L2:(L1#L2)-(256#L2),1:1) s R=0 q  ;XLLBFHP(2): or [not] (count of + before [...]) =mod (count of + within [...])= 256
s R=1,E=$e(P,I,$s(J:J-2,1:$l(P))) i $p(E,"]",1,$l(E,"]")-1)["+" s R=0 ;XLLBFHP(3): [not] (count of + withing ]...]) = 0[/noparse]

The following use of it:

[noparse]f  r R," " S R=$P(R," ") x XLLBFHP W $s(R="":" invalid",R:" ends",1:" doesn't end"),![/noparse]

produced the following output for various LBF programs:

[font="Fixedsys"][]                  ends
+                   ends
+[]                 doesn't end
+[+]                ends
[+++]               ends
+++++[+]            ends
+[++]               doesn't end
+++[+++++]          doesn't end
++++[+++]           ends
+++++[+[++]]        doesn't end
++[+[++]]           doesn't end
+[+[++]++++[+++]]   ends
+[+[++[+++]][++]]   doesn't end
+[[+++]]            ends
+[++]               doesn't end
++++[+++]           ends
+[+]++[++]          ends
+[[+]++[++]]        ends
+[[+]++[++]]+       ends
+[[+]++[++]+]       doesn't end
+[[+]++[++]+]+[+]   doesn't end
[[[[]               invalid
]]]][               invalid
+[+[++[+++][++]]    doesn't end
+[+][]]]]           ends[/font]

I use the output “ends” and “doesn’t end” as synonyms for HALTS and LOOPS in the previous posts description of halting program results.

 

If the runtime failure of a syntactically ill-formed LBF program is considered halting, then the “invalid” results above may be considered “ends”. Note, however, that although this program returns R=”” indicating that the program is ill-formed, it is not a validity checking program, so may also return “ends” and “doesn’t end” for syntactically invalid programs.

 

As mentioned in post #1, this program is an example of a halting program that doesn’t run the program it decides, but rather analyzes the input program’s structure.