Re: Do Write Once TM's Halt?


"Torben "Ægidius" Mogensen" <torbenm@xxxxxxxxxxxxx> wrote in message
news:7zejojhngm.fsf@xxxxxxxxxxxxxxxx
"Russell Easterly" <logiclab@xxxxxxxxxxx> writes:

"Torben "Ægidius" Mogensen" <torbenm@xxxxxxxxxxxxx> wrote in message
news:7zwt2dp54b.fsf@xxxxxxxxxxxxxxxx
"Russell Easterly" <logiclab@xxxxxxxxxxx> writes:


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.

A read-only TM is just a two-way finite automaton, so such questions
are trivial.

I know there are proofs for the decidability of the halting problem
for finite state machines, but they don't seem trivial to me.

For bounded tapes, they are trivial: you just enumerate all possible
states. For unbounded tapes, see below.

For example, I described loops in my proof. Loops can have very
complex structures. I also described repeating strings that can be
executed repeatedly in any combination. Again, this can lead
to very complex halting input tapes.

Do finite state machines require finite length input tapes?
I read one paper that says there is a FSM that halts if
the input tape has an even number of 1's.
This would only be possible if the input tape is finite.
My proof applies to infinitely long input tapes.

TM's don't have infinite tapes, they have unbounded tapes. The
important difference is that the tape at all times has finite support,
i.e., that it is blank outside a finite range (the size of which may
change during execution).

If you have a read-only tape, it too must be blank outside a certain
range, but this range doesn't change during execution. It is easy to
see that if a read-only TM with N states ever goes outside this range
by more than N spaces, it will not terminate. Hence, you can reduce
the termination problem to termination on a finite read-only tape,
which is, of course, trivial.

I was thinking of a tape like: 010101...
For example, a TM that halts if the input has an even number of 1's
would never halt on this input tape.
Such a TM would halt if the input only had a finite number of 1's on it.


Russell
- 2 many 2 count


.

Relevant Pages

  • Re: Do Write Once TMs Halt?
    ... I know there are proofs for the decidability of the halting problem ... for finite state machines, but they don't seem trivial to me. ... For unbounded tapes, see below. ... Do finite state machines require finite length input tapes? ...
    (comp.theory)
  • Re: Is the Halting Problem merely an ill-formed question?
    ... It either halts or it doesn't; ... THEY CAN write on their tapes. ... if (MalignantSelfReference(SourceCode, InputData)) ... that the Halting Problem is solvable, I am only at most attempting to show the ...
    (sci.logic)