random

[David C. Ullrich]

On Wed, 6 Jun 2001 18:23:17 +0200, "Alex Martelli" <aleaxit at yahoo.com>
wrote:

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

Whether there are countably many Turing machines or
uncountably many depends on whether the tape itself
is considered part of the TM. I've seen plenty of
definitions that appear to say that the tape is
part of the TM. I've also seen it said in plenty
of places that there are only countably many
Turing machines.

Could be that this means that people use the word
"TM" inconsistently. It would be a big surprise if
that were the one word in the language that _is_
used consistently. I have no interest in debating
whether it's correct or not to include the tape
as part of the machine or to regard the tape
as something external to the machine that the
machine manipulates.

_In_ the sense in which I was using the words, the
TM is the finite-state machine and the tape is something
that the TM manipulates.

Regarding the question of which usage is really the
usage that's been intended in all of this discussion:

Does there or does there not exist a TM which will
calculuate all the bits of Chaitin's Omega? You start
it running and the bits appear one by one, continuing
until you pull the plug.

(The standard answer is "no". If the tape is part
of the machine then the answer is "yes": You just
consider the TM that starts with Omega on the tape,
and which does nothing but echo its input.

I'll let you decide whether this means that "TM"
really has referred to the finite-state machine
or whether when people say there is no TM to
calculate Omega they should really say there
is no TM-with-initially-blank-tape. But if you
insist on calling the tape part of the "program"
(this is still in the non-UTM context), as
in

>and use [e.g] even squares
>of the tape as 'input' aka 'program')

then there _is_ a "program" to calculate the
bits of Omega. It seems to me that this indicates
that the usual meaning of the word "program"
is not what you're taking it to be. Don't
know whether it indicates anything like that
to you.)


>[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
>
>
>



David C. Ullrich
*********************
"Sometimes you can have access violations all the 
time and the program still works." (Michael Caracena, 
comp.lang.pascal.delphi.misc 5/1/01)