random

[William Tanksley]

On Thu, 07 Jun 2001 15:02:33 GMT, David C. Ullrich wrote:
>(William Tanksley) wrote:
>>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"?

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

This turns out to be a reasonable assumption; I've done some research, and
sure enough, TM programs are "defined" to be countable (it's actually an
unavoidable result).

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

>??? It seems to follow from statements in this paragraph that a UTM does
>not exist. It would require an "indefinite number" of states, but a UTM
>has a finite number of states. So there are no UTM's. Huh.

It would have been polite of you to continue talking -- either explain how
you reached that rather bizzare and obviously unintended conclusion, or go
on assuming that I meant something else (if you could figure out what that
something else was).  Keep in mind that I'm trying to figure this out,
too.  Bringing ego into it won't help.

I think you're questioning why you'd need an infinite number of states to
run your 'programs'.  The reason is that your programs aren't programs;
they're only data.  They have to be processed, converted into programs
somehow.  I'm not certain that this is computable; but if it is, it
requires some record of all the programs, since writing programs is
definitely not computable.

And /that/ is countably infinite.

>David C. Ullrich

-- 
-William "Billy" Tanksley