Re: Do Write Once TM's Halt?

"Russell Easterly" <logiclab@xxxxxxxxxxx> writes:

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

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.

A decision procedure needs finite input, and if your tape has infinite
support you can not give that tape to the decision procedure. So you
can only talk about decidability if you assume tapes with finite
non-blank cells, or at least tapes that have finite descriptions.

If you allow infinite tapes with finite descriptions, the decision
problem depends on which kind of descriptions you allow. It is, for
example, likely that you can decide termination if the tape
description is always of the form w^\omega, i.e., an infinite
repetition of a finite string w (such as your 010101..., which is
(01)^\omega). But if you allow descrition by arbitray TMs, the
problem is undecidable, not because of the complexity of the read-only
TMs but but because of the complexity of the general TMs used to
describe the input to the read-only TMs.

Torben

.

Relevant Pages

  • Re: DDS Tape problems
    ... All Are SCSI. ... but the tape is unreadable. ... I know none of this helps much toward solving the problem, ... >> The only other guess would be termination. ...
    (freebsd-questions)
  • Re: Quantum tape drive
    ... I'm preparing a cvsup as I write this:)) the tape drive's Alarm ... and Fault LEDs are lit up and then camcontrol devlist no longer shows ... usual suspects (terminator on the cable, SCSI IDs, etc.) but didn't ... How certain are you that its a termination problem? ...
    (freebsd-questions)
  • Re: DDS Tape problems
    ... If I try to read them I get card dump and tape ... I was trying to use Tekram SCSI adapter with same result. ... Termination should be fine. ... To unsubscribe, ...
    (freebsd-questions)
  • Re: SCO OpenServer 5 DDS-2 Sony SDT-5000 tape backup problems.
    ... > Tape has been configured using mkdev tape as follows ... Check the termination jumper, likely the cable has active termination ... with Compaq/HP tape drives that are working perfectly. ...
    (comp.unix.sco.misc)
  • Re: dodgy tape drive
    ... > I can use mt commands to rewind or retension the tape. ... or new drivers for your scsi controller. ... SCSI termination -- this is the bugaboo of scsi drives. ...
    (comp.os.linux.hardware)