Re: Do Write Once TM's Halt?


"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 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.


Russell
- 2 many 2 count


.