Re: Do Write Once TM's Halt?


"Chris Smith" <cdsmith@xxxxxxx> wrote in message
news:MPG.20380e203b25a2cb9897f2@xxxxxxxxxxxxxxxxxxx
r.e.s. <r.s@xxxxxxxxxxxxxxxx> wrote:
Yes, that must be true because your STMs can exhibit only
finitely many configurations. An emulating program could
simply run a given STM step-by-step until it either halts
or exceeds that number of steps -- if it hasn't halted by
that point, then it will never halt.

Or have I misunderstood something?

Nope, you're right. Russell's "Simple Turing Machine" is just a tiny
modification to a two-way DFA. There exist algorithms to obtain regular
expressions exactly describing the inputs on which it accepts, rejects,
and loops.


Halting Paths

I still don't have a proof the Halting Problem is decidable
for write once TM's, but I have a much better proof that
it is decidable for read only TM's.

Assume we have a TM that can only read from the tape and move
left or right one position on the tape.
The input tape is infinitely long and the language on the tape
contains only two symbols, 0 and 1.
The TM starts in state A and at position 1 on the tape.

I can finitely describe all input tapes that will cause
such a TM to halt.

Error processing: any input that causes the TM to move left
from the first position on the tape is considered a non-halting
input.

Assume we have a state transition table for the TM.
For example, in state A, on input 0, the TM moves Right
one position, and changes to state A would be encoded:

A:0RA

Example State Transition Table

State: Input Operation NewState
A:0RA
A:1RB
B:0LD
B:1RE
C:0RH
C:1LA
D:0RA
D:1RE
E:0RE
E:1RH
H: Halt

State H is the Halt state.


Halting Trees

We can form a tree of all paths that allow this TM to halt.
Start with state H and find all State/Input combinations
that transition to the Halt state.

C0 - can't be reached from state A
E1 - goes to halt

We know the TM starts in state A. The only way this TM can
halt is by following a path of State/Input combinations that
connects state A to state H.

State C is the only state that transitions to state C.
State C can't be reached from state A and will never be executed.
We can remove state C from the table and still describe the same TM.

A:0RA
A:1RB
B:0LD
B:1RE
D:0RA
D:1RE
E:0RE
E:1RH
H: Halt

We need to show that State/Input E1 can be reached from state A.

A1-B1-E1-Halt = Halting Path

A Halting Path is a series of State/Input combinations
that connect the start state, A, to the halt state, H.
No State/Input combination can appear more than once in a Halting Path
(see loops, below).
Halting paths don't depend on the operations performed by the TM.

The input string that causes the TM to execute a halting path
does depend on the operations the TM performs.
For the halting path A1-B1-E1, the first input must be a 1,
the position to the right must be a 1, and the next position
to the right must be a 1.

111000... = Halting input tape for A1-B1-E1-Halt.

We can form a tree containing all halting paths.
The halt state is the root of the tree.
Each branch is a State/Input that transitions to
the parent state. Terminal nodes are any node
that contains the start state, A.

E1
B1-E1, D1-E1, E0-E1
A1-B1-E1*, B0-D1-E1, B1-E0-E1, D1-E0-E1, E0-E0-E1
A1-B0-D1-E1*,A1-B1-E0-E1*, B0-D1-E0-E1, E0-E0-E0-E1
A1-B0-D1-E0-E1*

Loops

Notice the string E0-E0-...-E0-E1 can be infinitely long.
Certain State/Input combination can form loops.
For example, in a table where paths D1-E1 and E1-D1 existed
there could be a loop containing these two State/Inputs.
Loops can have any number of members.
I will represent loops by placing the loop in parenthesis.
A loop can be inserted in any halting path that contains
a member of the loop. For example:

A1-B1-E0-E1 contains E0 so: A1-B1-(E0)-E1

Impossible Strings

There are halting paths that can never be executed.
For example, consider A1-B0-D1-E1.
The first position must be a 1 for A1 to go to B0.
The next position to the right must be 0 for B0.
But, B0 moves the tape head left to position 1.
Luckily, D1 expects a 1 in that position and
moves the head right. E1 now expects a 1,
but we know this position is a 0 because of B0.
There is no string that can execute A1-B0-D1-E1.

All Halting Paths - strings:
A1-B1-E1 = 111
A1-B0-D1-E1 = impossible string
A1-B1-(E0)-E1 = 110x1
A1-B0-D1-(E0)-E1 = 10x1

Repeating Paths

The TM starts in state A, but it can also enter
state A at some future step. To account for this,
we need to describe all paths that connect state A
to state A.

A0
A0-A0*, D0-A0
B0-D0-A0
A1-B0-D0-A0*

A1
A0-A1*, D0-A1
B0-D0-A1
A1-B0-D0-A1*

Repeating Paths - strings:
(A0) - 0x
(A0)-A1 - 0x1
A1-B0-D0-A0 - impossible string
A1-B0-D0-A1 - impossible string


Halting Input Tapes

A halting input tape is any tape that starts with
zero or more combinations of repeating strings
followed by a halting string.

The halting input tapes for this example are:

111 ...
110x1 ...
10x1 ...
0x111 ...
0x110x1 ...
0x10x1 ...

where 0x means one or more 0's
and ... means any input.


Non-Halting Input

011000... does not match any halting string.


The halting paths for a TM do not depend
on the operations performed by the TM.

Is it true that any TM must follow
a halting path to halt, regardless of the
operations the TM performs?


Russell
- 2 many 2 count


.

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... to state the facts and point to the documentation for the sake of ... after you started the machine running on the tape, ... on input w) loops iff it doesn't halt. ... Loops on input-descriptions of those machines that DON'T ...
    (sci.logic)
  • Re: Do Write Once TMs Halt?
    ... Does A Write Once TM Halt? ... OR the current tape position with 0 and move right one position. ... The TM can not halt unless there is at least one halting path ... to enter a "loop" that it never leaves. ...
    (comp.theory)
  • Re: Smaller UTM than Rule110
    ... cater to your obsessions, not mine. ... > specified mark at a specified point on the tape. ... include the enhancement of an oracle that is aware ... What makes you think the tape has _room_ for a halt ...
    (comp.theory)
  • Re: PROOF that numbers are countable
    ... Well, all programs eventually *do* halt (when the power goes out, ... a series of symbols readable from and writable to tape. ... > We can get the UTM to run the UTM represented on the tape. ... >> usual proof of diagonalization doesn't quite work here, ...
    (comp.theory)
  • Re: Proof that the diagonal is useless, redundant, noise,
    ... If the machine is failing to halt then you NEVER KNOW ... for which the TM loops on the input, ... >> first parameter on the second. ... >> There is no rightmost digit TO WHICH to add the 1. ...
    (sci.logic)