Re: A Class of Non-Halting TMs

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

Date: Tue, 13 Jan 2004 19:15:59 -0800

"Jim Nastos" <nastos@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.0401131159540.8162-100000@eva117.cs.ualberta.ca...
> On Tue, 13 Jan 2004, Russell Easterly wrote:
>
> > Make a history of the steps this SM performs
> > that contains the following information:
> > Step, current state, input, and tape position.
>
> Essentially, you are using at technique commonly invoked
> in a lot of proofs in complexity theory in which one counts
> the total number of "internal configurations" of a space-bounded
> machine.

Thanks.
I assumed my method was similar to known methods.
Can you give references?

> For a machine with N states and uses at most M tape cells using an
> alphabet of 'a' symbols, the number of possible tape configurations
> is a^M, number of tape positions for the tape head is M, number of
> possible states the machine can be in is N, so the total number of
> configurations is N*M*(a^M). If a turing machine ever exceeds this
> number of steps, then it MUST have repeated an internal configuration
> and so it will loop forever... and you could always keep a running
> total to the max number of tape cells used.

Less than an hour after I posted I found a mistake in my method.
It is amazing how things that seem obvious become less obvious
when you describe them to other people.

I think the argument you give above may be false.
Consider a TM that prints the first ten million
digits of PI and then halts.

3.1415926535897932384626433832795...

Now, assume this TM doesn't print one long list of digits.
Instead, it writes three digits forward then three digits backward:

314
951
265
853
...

a=[0,1,...,9]
M=3
Assume N=100.
N*M*(a^M) = 100*3*(10^3) = 300,000

We can assume that every 3 digit number between 000 and 999
is written. (This may not be a good assumption. PI may not be
the best sequence of digits to choose. I could replace PI with
another sequence like 01011011101111011111...)

Clearly, this TM executes more than 300,000 steps.
So, "If a turing machine ever exceeds this number of steps,
then it MUST have repeated an internal configuration
and so it will loop forever" may not be true.

> This is essentially what you are doing, except this is a bit stronger,
> I think.
> Also, I think your testing for non-halting depends on REPEATING itself,
> but many (in fact most) non-halting machine histories will not repeat
> themselves.
>
> (Aside: I say 'most' will not repeat themselves because of this
> intuition: if you take a nonhalting machine history which eventually
> repeats, you can take the step indexes as you are using for step 1, 2, 3,
> etc, and build their history as step 5,6,7,8,9,10,11,5,6,7,8,9,10,
> 11,5,6,... etc. Remove the commas and put a decimal point in front of the
> sequence of numbers and you build a rational number. The number of such
> repeatins histories, then, is mappable to a subset of rational numbers,
> whereas the number of possible [infinite-lengthed] histories is
> uncountable.)

Yes, this seems obvious.
Unfortunately, I now have trouble believing proofs based on
the countability of the rationals vs the uncountability of the reals.

> > Question:
> > Are there non-halting SMs with a finite state
> > transition table that this method can't determine
> > are non-halting?
>
> Yup. Make a machine that will take a all-0-tape and write
> 010110111011110111110... essentially, it counts in unary, separating
> numbers with a 0-symbol. This is never have one of the 'loops' that
> you are detecting for.

I knew the answer must be yes.
I was trying to construct such a SM.
I have found several since yesterday.

The flaw in my method is the assumption that the SM
has not "tampered" with the input tape outside of the
loop I identify. The SM could write a "1" somewhere
"ahead" of the loop that will cause it not to loop.

Consider this SM:

State / Input / Operation / New State
0 / 0 / 1 / 1
1 / 1 / R / 2
2 / 0 / R / 3
3 / 0 / R / 4
4 / 0 / R / 5
5 / 0 / 1 / 5
5 / 1 / L / 6
6 / 0 / L / 6
6 / 1 / 1 / 0

All undefined state/input combinations halt.

History Table
Step) State / Input / Position / Op / New / Input Tape

0) 0 / 0 / 0 / 1 / 1 / 0...
1) 1 / 1 / 0 / R / 2 / 10...
2) 2 / 0 / 1 / R / 3 / 10...
3) 3 / 0 / 2 / R / 4 / 100...
4) 4 / 0 / 3 / R / 5 / 1000...
5) 5 / 0 / 4 / 1 / 5 / 10000...
6) 5 / 1 / 4 / L / 6 / 10001...
7) 6 / 0 / 3 / L / 6 / 10001...
8) 6 / 0 / 2 / L / 6 / 10001...

My method will say steps 7-8 repeat:
7) x = 2-3 = -1
8) 2-0 : 1-0

This SM does halt:
9) 6 / 0 / 1 / L / 6 / 10001...
10) 6 / 1 / 0 / 1 / 0 / 10001...
11) 0 / 1 / Halts

To avoid this problem I have to keep track
of the largest position written to by the SM.

Let j be the current step.
Let w = largest position written to by the SM before step j.
Let i-j be a sequence of steps.
Let P(i) be the position of the tape at step i.

x=P(j)-P(i)

I have to show that P(k)+x > w for some k: i <= k <= j.
I think my method works with this additional assumption.

Here is an example of a SM that my method can not
show is non-halting:

State / Input / Operation / New State
0 / 0 / 1 / 1
0 / 1 / 0 / 1
1 / 0 / R / 2
1 / 1 / R / 2
2 / 0 / 1 / 2
2 / 1 / L / 0

History Table
Step) State / Input / Position / Op / New / Input Tape
0) 0 / 0 / 0 / 1 / 1 / 0...
1) 1 / 1 / 0 / R / 2 / 10...
2) 2 / 0 / 1 / 1 / 2 / 10...
3) 2 / 1 / 1 / L / 0 / 110...
4) 0 / 1 / 0 / 0 / 1 / 110...
5) 1 / 1 / 0 / R / 2 / 010...

Do steps 1-5 loop?
1) x = 0-0 = 0
2) 1-0 : 1-1
no loop

6) 2 / 1 / 1 / L / 0 / 010...
Do steps 3-6 repeat?
3) x = 1-1 = 0
4) 0-1 : 0-0
no loop

7) 0 / 0 / 0 / 1 / 1 / 010...
Do steps 0-7 repeat?
0) x = 0-0 = 0
1) skip
2) 1-0 : 1-1
no loop

8) 1 / 1 / 0 / R / 2 / 110...
9) 2 / 1 / 1 / L / 0 / 110...

Reduced history table: input/position
0) 0 / 0
2) 0 / 1
4) 1 / 0
6) 1 / 1
7) 0 / 0
9) 1 / 1

Steps 4-7 are unstable.
Steps 3-9 can't be a loop.
Steps 6-9 could repeat:
6) x = 1-1 = 0
7) 0-0 : 0-1
no loop

10) 0 / 1 / 0 / 0 / 1 / 110...
Steps 4-10 can not be a loop.

11) 1 / 0 / 0 / R / 2 / 010...
12) 2 / 1 / 1 / L / 0 / 010...

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

Steps 8-11 are unstable.
Steps 6-12 can't repeat.
Steps 9-12 may repeat:
9) x = 1-1 = 0
10) 0-1 : 0-0
no loop

0) 0 / 0 / 0 / 1 / 1 / 0...
1) 1 / 1 / 0 / R / 2 / 10...
2) 2 / 0 / 1 / 1 / 2 / 10...
3) 2 / 1 / 1 / L / 0 / 110...
4) 0 / 1 / 0 / 0 / 1 / 110...
5) 1 / 1 / 0 / R / 2 / 010...
6) 2 / 1 / 1 / L / 0 / 010...
7) 0 / 0 / 0 / 1 / 1 / 010...
8) 1 / 1 / 0 / R / 2 / 110...
9) 2 / 1 / 1 / L / 0 / 110...
10) 0 / 1 / 0 / 0 / 1 / 110...
11) 1 / 0 / 0 / R / 2 / 010...
12) 2 / 1 / 1 / L / 0 / 010...
13) 0 / 0 / 0 / 1 / 1 / 010...
14) 1 / 1 / 0 / R / 2 / 110...

This SM can not halt because it has no halt state.
It appears my method can not show that it repeats.
(Doing all this by hand is a pain.)

According to Jim Nastos' formula this SM must repeat:

N = 3
M = 2
a = 2
N * M * (a^M) = 24

I may have to break down and write a program
to see if this is true.

Notice that starting at step 3 this SM repeats the states: 201.
The input starting from step 3 goes: 111, 101, 110, 101.
Even if this SM repeats steps 3-27, it will never repeat
the initial segment (steps 0, 1, and 2).
As near as I can tell, there is no limit on how large
this initial non-repeating segment can be.

Russell
- 2 many 2 count

Relevant Pages

  • A Class of Non-Halting TMs
    ... A Class of Non-Halting TMs ... This tape can only contain 0's or 1's. ... Machine History Table ... Are steps 4 through 7 a loop? ...
    (comp.theory)
  • Re: acceptance of forth
    ... before entering an infinite loop (i.e. ... repeat jumps to after while instead of after begin?) ... begin..while..repeat has multiple templates (which, ... circumstances where I consulted the books. ...
    (comp.lang.forth)
  • Re: OpenVMS I64 ISV application count now over 500
    ... Compaq management apparently never followed up on as some here had stated ... Defamation where defamation is due - that's my motto. ... > history, it has little to no bearing on what we are doing now. ... doomed to repeat it." ...
    (comp.os.vms)
  • Re: RFC: About error handling - WAS: Re: A remobjects wtf...
    ... Of course in this example (and probably in most cases, as there is some condition that determines whether you need to retry) it could be replaced with a test for a valid BaudRate in 'until'. ... You could be against repeat and while in general with the same argument. ... I would also say that your 'Retry' examples resembles these much more (You wouldn't need 'goto Succeeded', would you?): ... 'break') applies to this 'fake' loop, ...
    (borland.public.delphi.non-technical)
  • Re: Using variables
    ... This code mostly avoids stack gymnastics by using the pseudoregisters p and q for the addresses, representing data whose flow isn't LIFO. ... We could use v-v-dot as a factor, but here we can save some address arithmetic in the outer loop by noting that if p contains the address of a matrix, after iterating it points to the next row of the matrix automatically. ... they use LSE's beloved universal loop word: "repeat". ... you sometimes need to break out of an "iterate" loop prematurely. ...
    (comp.lang.forth)