A Class of Non-Halting TMs

From: Russell Easterly (logiclab_at_comcast.net)
Date: 01/13/04 

Date: Tue, 13 Jan 2004 02:44:39 -0800

A Class of Non-Halting TMs

I describe a large class of TMs that
can be proven to be non-halting.
This is not a solution to the halting problem.

I will describe a subset of TMs.
Call these Simple Machines, SM.

A SM can perform five operations:

0) Print 0
1) Print 1
L) Move Left
R) Move Right
H) Halt

(a SM halts by error if it tries to move left
from the initial position.)

A SM can read and write to a tape.
This tape can only contain 0's or 1's.
A "blank" tape is defined as a tape
that only contains 0's.

Example of State Transition Table of an SM.

State / Input / Operation / New State
0 / 0 / R / 1
0 / 1 / 0 / 0
1 / 0 / 1 / 0
1 / 1 / H / 0

Does this SM halt when given a blank tape?

Make a history of the steps this SM performs
that contains the following information:
Step, current state, input, and tape position.

An SM always starts in state 0 at position 0.

Machine History Table
Step) State / Input / Position / Operation / New State / Input Tape
0) 0 / 0 / 0 / R / 1 / 0...
1) 1 / 0 / 1 / 1 / 0 / 00...
2) 0 / 1 / 1 / 0 / 0 / 01...
3) 0 / 0 / 1 / R / 1 / 00...

This SM can be shown to be non-halting.

Before each step we take the current
state/input combination and search the
history list for this combination.

Step 3 has the same state and input
as step 0. The tape is at position 1
for step 3 and position 0 for step 0.

Take the difference between these
two tape positions and call it the
offset, x=1-0=1.

Add x to the tape position in step 1.
This new position is 2.
Examine position 2 on the current tape.
It contains a 0 which is the same as
the input in step 1.

Add x to the tape position of step 2.
This new postion is 2 which we just examined.

The action of the SM is determined
completely by the history table until
the SM moves left or right!
We can skip step 2.

Similarly, we can ignore step 3
because the SM has not changed
the tape position.

We have now shown that this SM
will repeat the following
state/input combinations forever:

0/0, 1/0, 0/1

A more complicated example:

SM State Transition Table:

State / Input / Operation / New State
0 / 0 / R / 1
0 / 1 / R / 1
1 / 0 / 1 / 3
1 / 1 / R / 2
2 / 0 / 1 / 0
2 / 1 / H / NA
3 / 0 / R / 2
3 / 1 / L / 2

The only halting state/input is 2 / 1.

History table for this SM:

Step) State / Input / Position / Operation / New State / Input Tape

0) 0 / 0 / 0 / R / 1 / 0
1) 1 / 0 / 1 / 1 / 3 / 00
2) 3 / 1 / 1 / L / 2 / 01
3) 2 / 0 / 0 / 1 / 0 / 01
4) 0 / 1 / 0 / R / 1 / 11
5) 1 / 1 / 1 / R / 2 / 11
6) 2 / 0 / 2 / 1 / 0 / 110

Steps 3 through 6 could repeat.

Step) Old position-Old input : New position-New input
3) x=2-0=2
4) skip (same position as step 3)
5) 1-1 : 3-0

The current tape differs from the history so we
can not say this is a loop.
We continue the history table:

7) 0 / 1 / 2 / R / 1 / 111

Are steps 4 through 7 a loop?
4) x=2-0=2
5) 1-1 : 3-0
Again this is not a loop.
So we continue the history table:

8) 1 / 0 / 3 / 1 / 3 / 1110

Are steps 1 through 8 a loop?
1) x=3-1=2
2) skip
3) 0-0 : 2-1
Again this is not a loop.
So we continue the history table:

9) 3 / 1 / 3 / L / 2 / 1111

Are steps 2 through 9 a loop?
2) x=3-1=2
3) 0-0 : 2-1
No loop so continue:

10) 2 / 1 / 2 / Halts / NA / 1111

This machine halts after 11 steps.

We can reduce the history table to:
Step) input / position
0) 0 / 0
1) 0 / 1
2) 1 / 1
3) 0 / 0
4) 1 / 0
5) 1 / 1
6) 0 / 2
7) 1 / 2
8) 0 / 3
9) 1 / 3

Now eliminate all steps that are at
the same position as the previous step.
0) 0 / 0
1) 0 / 1
3) 0 / 0
5) 1 / 1
6) 0 / 2
8) 0 / 3

Steps 0 and 3 both require that
position 0 of the current tape be a 0.
These steps do not conflict.

Steps 1 and 5 require tape position 1 to
have conflicting values. Steps 1 though 5
can't be part of any loop because the
current tape is static. A conflicting
(unstable) portion of the reduced history
tape can't be part of any loop.

Make the SM above non-halting by removing the halt state/input.
Change the state transition table entry:
2 / 1 / H / NA
to:
2 / 1 / R / 1
and continue the history table.

Step) State / Input / Position / Operation / New State / Input Tape
0) 0 / 0 / 0 / R / 1 / 0
1) 1 / 0 / 1 / 1 / 3 / 00
2) 3 / 1 / 1 / L / 2 / 01
3) 2 / 0 / 0 / 1 / 0 / 01
4) 0 / 1 / 0 / R / 1 / 11
5) 1 / 1 / 1 / R / 2 / 11
6) 2 / 0 / 2 / 1 / 0 / 110
7) 0 / 1 / 2 / R / 1 / 111
8) 1 / 0 / 3 / 1 / 3 / 1110
9) 3 / 1 / 3 / L / 2 / 1111
10) 2 / 1 / 2 / R / 1 / 1111
11) 1 / 1 / 3 / R / 2 / 1111
12) 2 / 0 / 4 / 1 / 0 / 11110

Steps 3-12 and 6-12 could be loops.

Reduced history table:
Step) input / position
0) 0 / 0
1) 0 / 1
3) 0 / 0
5) 1 / 1
6) 0 / 2
8) 0 / 3
10) 1 / 2
11) 1 / 3
12) 0 / 4

Steps 6 and 10 conflict.
Steps 8 and 11 also conflict.
We only need to keep track of the
unstable section of the tape with
the largest initial step.

Steps 3-12 can not be a loop
because they contain steps 8-11.
Steps 6-12 are not a loop for
the same reason.
Continue history table:

13) 0 / 1 / 4 / R / 1 / 11111
Steps 4-13 and 7-13 can not be loops.

14) 1 / 0 / 5 / 1 / 3 / 111110
Steps 1-14 and 8-14 can not be loops.

15) 3 / 1 / 5 / L / 2 / 111111
Steps 2-15 can not be a loop.

Steps 9-15 could be a loop.
9) x=5-3=2
10) 2-1 : 4-1
11) 3-1 : 5-1
12) 4-0 : 6-0
13) skip
14) 5-0 : 7-0
15) skip

This SM repeats the following state/inputs:
3/1, 2/1, 1/1, 2/0, 0/1, 1/0

Conjecture:
This method will never say that a halting SM
is non-halting.

Question:
Are there non-halting SMs with a finite state
transition table that this method can't determine
are non-halting?

Russell
- 2 many 2 count

Relevant Pages

  • Re: A Class of Non-Halting TMs
    ... >> Step, current state, input, and tape position. ... and so it will loop forever" may not be true. ... if you take a nonhalting machine history which eventually ... My method will say steps 7-8 repeat: ...
    (comp.theory)
  • Re: Raw_input with readline in a daemon thread makes terminal text disappear
    ... loop in separate thread. ... having a command history or the use of backspace etc. ... control of the command-line while raw_input is accepting input - at least this ... I worked around it by making the input loop ...
    (comp.lang.python)
  • Re: no add link into history link....
    ... > should not add an entry to the history. ... >> History link the macro make for each record ... >> DoEvents ...
    (microsoft.public.excel.programming)
  • Re: McCartney bio...update.
    ... the song and knew the sound he wanted to achieve. ... On any tape recorder, if you cover ... John's voice through a Leslie speaker, because he'd said to me "I want ... and put one loop on each, and I fed each of those machines into the ...
    (rec.music.beatles)
  • Re: a row-level operator for copying?
    ... code sample below, these tables are atest and atest_history). ... but you should move the actual insert/delete after the loop. ... and BULK INSERT them into the history table and BULK ...
    (comp.databases.oracle.misc)