Re: My claim on Omega's defn

From: Arthur Fischer (arthurfischer_at_sym.ca)
Date: 01/31/05 

Date: Sun, 30 Jan 2005 22:19:55 -0500

rupertmccallum@yahoo.com wrote:

> How do you prove that a prefix-free universal Turing machine exists?

I am _not_ an expert in this, so take this all with a grain of salt.

Essentially, the notion of "prefix fee" concerns the domain of the
(partial) function the TM may be considered to compute. Of course, with
a standard TM, based on the deterministic nature, there may not be a
good way to ensure that such a condition holds, and so we need to make a
precise definition of what the domain of this function should be. What
I have gathered is that Chaitin modified the definition of a Turning
Machine slightly so that one would have a handle on a natural definition
of the domain of the function that the TM computes.

Instead of one tape that does all of the work, he has three: a
dedicated read-only input tape, a dedicated write-only output tape, and
a work tape. There are a couple of other technicalities, such as the
head only moves right-wards on the input and output tapes.

For a general TM, to speak of the function it computes, all you need to
do is look at the bit string close to where the read/write head halts,
and that's it. For these Chaitin machines, a few extra conditions have
to be satisfied, one of which is that the TM is reading the blank after
the original input on the input tape. I have not gone through all of
the details, but if you give such a TM the input

10010----

and the halting conditions are satisfied, so that 10010 is in the
domain, then because of the nature of the input tape, feeding the TM

10010001---

will cause a halt after going through the "10010" portion, but then the
computing criteria will not be satisfied for this run (not reading the
blank after the input). In this way, you can use the determinism of the
TM to ensure that its domain in prefix-free.

Now, of course, you need to ensure that for this universal TM the set of
encodings of TM is prefix-free. This can fairly easily be done by
ending each encoding by a special "End Of Turing Machine" bit sequence,
and then using some sort of bit-stuffing to ensure that the this EOTM
sequence does not appear in the actual encoding.

This all said, you may have been questioning the notion of
"self-delimiting," and I am not really in a position to discus this (by
which I mean, this is really outside my area of expertise, and I have
not gone through the details of this myself), hopefully others are.
Again, there are numerous non-Mathworld references available on the
'net, and a number have been pointed to in similar threads in this/these
newsgroup(s).

Cheers!
__
Arthur

Relevant Pages

  • Re: My claim on Omegas defn
    ... Instead of one tape that does all of the work, ... one of which is that the TM is reading the blank after ... TM to ensure that its domain in prefix-free. ... sequence does not appear in the actual encoding. ...
    (sci.logic)
  • Re: My claim on Omegas defn
    ... Instead of one tape that does all of the work, ... one of which is that the TM is reading the blank after ... TM to ensure that its domain in prefix-free. ... sequence does not appear in the actual encoding. ...
    (comp.theory)
  • Re: Audacity and Gentoo
    ... It's not like reading on a computer monitor, ... It can back up to disc, tape, and CD/DVD and has simple programmes ... DAT is good, the drives are expensive but I am lucky enough to have ...
    (uk.comp.os.linux)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... > this question (to fully solve the Halting Problem) would require ... two parameters on its tape (separated by an agreed-upon ... The second is a number encoding ... if it sees a "1" in the first cell of the tape, ...
    (sci.logic)
  • Re: dd behaving inconsistently
    ... It *always* specifies the record length when reading. ... Tape blocks *can* be variable in size. ... do a readinto a buffer that you 'know' is bigger than the largest possible ... If you're going through the standard library 'buffered' ...
    (comp.unix.shell)
Loading