random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b1e4957.3040319 at nntp.sprynet.com...
> On Tue, 05 Jun 2001 20:42:47 GMT, wtanksle at dolphin.openprojects.net
> (William Tanksley) wrote:
>
> >On Tue, 05 Jun 2001 15:09:25 GMT, David C. Ullrich wrote:
> >>But this question is not meant to be rhetorical: We have a syntax where
> >>the valid programs are exactly finite sequences of 0's terminated by a
1.
> >>Does this count as "self-delimiting"?
> >
> >Yes, but I don't think it counts as a UTM program.  There are only
> >countably many possible programs for this machine, while a UTM can run
> >uncountably many.
>
> Um. Some of these "programs" have infinite length, then? If they

I think a Universal Turing Machine should by definition
accept programs of infinite length.  It has an infinite
length tape and the program is written there; is there
any clause I'm forgetting which says the tape cannot have
an infinite number of symbols on it when the run starts?

> all have finite length then there's only countably many - that's
> even if the length is unbounded. If a UTM actually runs programs
> of infinite length then fine, but I can't imagine what it means
> to run such a program.

Some of those runs will in fact halt (not all of the
program steps that are on the tape need be reachable,
surely?), other won't, some of those that don't halt
will reach all steps on the tape.  I don't see what
is strange about that, so I may be missing something.

Let's take an example to fix ideas.  We won't even
take a Universal TM, just a plain TM.  Symbols on the
tape mean (summarizing a little):
    0    print a 0, overwrite the 0 with NOP, get to state A
    1    print a 1, overwrite the 1 with NOP, get to state A
    X    get to state B, move right
    NOP  if state B move right, if state A move left
    H    halt
A typical program is an X followed by a sequence of
0 and 1 (there may be NOP's there, but they have no
effect -- there may be X's, which also have no
effect on the output -- there may be H's, of course,
to halt the program).

If the program is finite, this non-universal Turing
Machine prints a finite sequence of 0's and 1's then
halts.  If the program is infinite but contains a H
somewhere, ditto -- nothing right from the H is even
considered.  If the program is infinite and contains
no 'H', we have a non-halting program, which just
keeps printing 0's and 1's as its original "source
code" (:-) specifies.

It seems clear to me that this IS a pretty ordinary
Turing Machine.  Am I missing something?

The sets of programs for this TM seems to be in a
natural correspondence with all reals between 0
and 1.  Many programs output the same real, of
course, since we have the ability to place NOP's,
but by a typical Cantor diagonal argument the cardinality
of the set of programs would seem to be that of the
reals (am I missing something here?) as we can
easily encode each program into a real (between
0 and 1, say) by using 3 bits to encode each
symbol and just catenating them.

By definition of Universal, a UTM should be able
to execute these programs (as well as many others).
So, the set of programs a UTM can execute has a
cardinality of at least that of the reals.  Since
a UTM's program is an enumerable sequence from a
finite alphabet, the cardinality of the set of
programs seems to be EXACTLY that of the reals
(same construction as above).

It's been a LONG, LONG time since I had to wrestle
with such stuff, so please DO let me know what
subtle clauses in the various relevant definitions
I'm missing, if any...

(Ah, to be 20 again...!-)


Alex