Re: Do Write Once TM's Halt?

Does A Write Once TM Halt?

Definition of a Write Once TM

The TM reads the symbol at the current tape position.
Depending on the symbol and state of the TM, it can
perform one of the following operations:

1) OR the current tape position with 0 and move right one position.
2) OR the current tape position with 1 and move right one position.
3) OR the current tape position with 0 and move left one position.
4) OR the current tape position with 1 and move left one position.

The TM can then switch to another state.
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.
The tape is blank and contains only 0's.

I can finitely describe all "halting paths" that will cause
such a TM to halt. In particular, given a blank tape
(a tape of all 0's), there is exactly one halting path
for a given TM that halts.

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 OR's the input
with 1 and moves Right one position, and then changes to state B.
This would be encoded:

State: Input OR Move NewState
A:01RB

Example State Transition Table

State: Input OR Move NewState
A:01RB
A:11RC
B:00LD
B:11RE
C:01RH
C:11LA
D:00RA
D:11RE
E:01RE
E:11RH
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 = C:01RH
E1 = E:11RH

We know the TM starts in state A and that a blank tape
will have a 0 at position 1 when the TM starts.
The only way this TM can halt is by following a path of
State/Input combinations that connects State/Input A0 to state H.
The TM can not halt unless there is at least one halting path
from A0 to H.

C0
A1-C0
C1-A1-C0
A1-C1-A1-C0
(C1-A1)-C0
There is no path connecting A0 to C0.
State/Input C0 can never be executed.

E1
B1-E1
A0-B1-E1-Halt

There exists a possible halting path.
Now generate all halting paths.

E1
B1-E1, D1-E1, E0-E1
A0-B1-E1*, B0-D1-E1, B1-E0-E1, D1-E0-E1, E0-E0-E1
A0-B0-D1-E1*, A0-B1-E0-E1*, B0-D1-E0-E1, (E0)-E1
A0-B0-D1-E0-E1*

Halting paths

A0-B1-E1
A0-B0-D1-E1
A0-B1-(E0)-E1
A0-B0-D1-(E0)-E1

We need to know all paths that connect state/input A0
to state/input A0.

A0
C1-A0, D0-A0
A1-C1-A0, B0-D0-A0
C1-A1-C1-A0, D0-A1-C1-A0, A0-B0-D0-A0*
(A1-C1)-A0, B0-D0-A1-C1-A0
A0-B0-D0-A1-C1-A0*

Repeating paths
A0-B0-D0-A0
A0-B0-D0-(A1-C1)-A0

We can now ask which halting path this TM will
follow when given a blank input tape.
There can only be one such path if the TM halts.

The TM might not halt even if it does follow
a halting path. It is possible for the TM
to enter a "loop" that it never leaves.

There are three possibilites when a TM enters
a loop on the halting path:

1) The TM never leaves the loop
2) The TM leaves the loop along a non-halting path
3) The TM leaves the loop along a halting path

The TM will never halt in conditions (1) and (2).
We can always determine which of these three states
is true for a given TM on a given input tape on a given loop.
(This is a conjecture.)

A halting path can have several loops.
We can determine whether the TM halts for each loop.

To check for this possibility of loops I will use a history tape.
The history tape keeps the following information:

Step - number of operations TM has performed
State - state of TM on this step
Input - Input read on this step
Position - Position of tape head on this step

State: Input OR Move NewState
A:01RB
A:11RC
B:00LD
B:11RE
C:01RH
C:11LA
D:00RA
D:11RE
E:01RE
E:11RH
H: Halt

History Tape:

1) A0: ^0000000....
2) B0: 1^000000....

TM must be in repeating paths A0-B0-D0-A0 or A0-B0-D0-(A1-C1)-A0
or in halting paths A0-B0-D1-E1 or A0-B0-D1-(E0)-E1.
Halting paths A0-B1-E1 and A0-B1-(E0)-E1 are impossible
(unless the TM is in a repeating path).

3) D1: ^1000000....

TM can not be in any repeating path and must be in halting paths
A0-B0-D1-E1 or A0-B0-D1-(E0)-E1.

4) E0: 1^000000....

TM must be following halting path A0-B0-D1-(E0)-E1.
Does the TM ever leave the loop (E0)?

5) E0: 11^00000....
6) E0: 111^0000....

We see this TM will never leave the loop (E0) and
will never halt on a blank input tape.


Russell
- 2 many 2 count


.

Relevant Pages

  • 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: Do Write Once TMs Halt?
    ... then it will never halt. ... Assume we have a TM that can only read from the tape and move ... No State/Input combination can appear more than once in a Halting Path ... (see loops, below). ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... :>> including the subject of the halt analysis. ... The word "caller" DOES NOT EXIST in the paper! ... The answer it returns is the contents of its tape ... : My method eliminates the prior prohibition for: ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... If you make this assumption then eliminating the undecidability ... opposite is of what Halt determines. ... The "usual conventions" part is the error on your part. ... Assuming that the Halt Analyzer has a tape, ...
    (sci.logic)