random

[David C. Ullrich]

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

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

I don't think that it should. It's supposed to be able to
"emulate" an arbitrary TM. It takes only finitely much
space to define a given TM - I don't see any _reason_
to use infintely much space to hold finitely much data.

What you're calling part of the program here and elsewhere
I would regard as part of the input stream to a program,
not part of the program itself. I would not presume
to insist that my usage is "correct" here, but that's
what I meant (and also if an arbitrary input stream
is allowed as part of a TM then there _does_ for
example exist a TM that calculates the bits of 
Omega one by one.)

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

I really am _not_ an authority on the definitions
here. But my impression is that people do use
the phrase "TM" ambiguously: The definition of
"TM" sounds like the tape is part of the TM,
but when people talk about how many TM's there
are and what a TM can and cannot do it seems clear
they are no including that tape as part
of the TM, otherwise everything they say would
be nonsense.

>(Ah, to be 20 again...!-)
>
>
>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)