random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b1e43f4.1661099 at nntp.sprynet.com...
    ...
> I didn't bother mentioning the semantics before getting straight
> whether the syntax counted as "self-delimiting". It is very
> easy to design a Turing-complete programming language where
> the syntactically valid programs are exactly the bitstrings
> consisting of all 0's terminated by a 1. Assunming that

If so, then the set of Turing-machine program must be
enumerable (alpha-0).  But is it?

> "arbitrary binary data" means only finitely much binary
> data that's no problem.

I think there is the rub.

What I find in the "Stanford Encyclopedia of Philosophy", e.g:

"""
A Turing machine is an abstract representation of a computing
device. It consists of a read/write head that scans a (possibly
infinite) two-dimensional tape divided into squares, each of
which is inscribed with a 0 or 1. Computation begins with the
machine, in a given "state", scanning a square. It erases what
it finds there, prints a 0 or 1, moves to an adjacent square,
and goes into a new state. This behavior is completely determined
by three parameters: (1) the state the machine is in, (2) the number
on the square it is scanning, and (3) a table of instructions. The
table of instructions specifies, for each state and binary input,
what the machine should write, which direction it should move in,
and which state it should go into. (E.g., "If in State 1 scanning
a 0: print 1, move left, and go into State 3".) The table can list
only finitely many states, each of which becomes implicitly defined
by the role it plays in the table of instructions. These states are
often referred to as the "functional states" of the machine.
"""

Finite-state machine at the 'core', infinite tape (sorry I
used more than two tape symbols in my previous post and
assumed an 'output' that was not to the tape itself, but
I believe it's easily proved that you can map any finite
number of tapesymbols to two, and use [e.g] even squares
of the tape as 'input' aka 'program' and odd ones for
'output', etc, etc).  This is the TM (not yet necessarily
Universal, all depends on that FSM at the core) as I
recalled it, after lo these many years...

[E.g. to treat even and odd squares differently you "just"
have to split the core FSM appropriately, so it 'remembers'
whether it's on an odd or even square of the tape -- that
is just one bit so at most it doubles the FSM's states --
doing it all with 0 and 1 is unwieldy but you can move
to any finite number of symbols by using N squares with
0 and 1 to represent up to 2**N distinct symbols and
complicating the FSM accordingly -- etc, etc... but of
course it's possible to slip in one of these "etc"s:-)]


Alex