random

[William Tanksley]

On Wed, 06 Jun 2001 15:19:36 GMT, David C. Ullrich wrote:
>(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 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.

Hmm...  I'm pretty sure that programs for an UTM could be infinite length;
however, let's suppose that for the purposes of omega they couldn't be
(IMO a reasonable supposition).  Then my proof is clearly invalid.

However, your machine still isn't a UTM, because in order to process an
indefinite number of possible programs it has to have an indefinite number
of states.  It has to be able to count up to little-omega (otherwise it
won't know what program it's executing), but the only way to do that is
with an infinite number of states.  And an UTM has a finite number of
states.

>David C. Ullrich

-- 
-William "Billy" Tanksley