random

[David C. Ullrich]

On Wed, 06 Jun 2001 22:27:32 GMT, wtanksle at dolphin.openprojects.net
(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"?
>
>>>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.

You might note for example that Chaitin says out loud that
Omega is the sum of 2^(-length(p)), where p runs over all
programs that halt. (The notation he uses in the place I
saw this is |p|, and I don't recall him defining |p|. But
if we set |p| = length(p) then that formula _does_ give
Omega. So if he means to allow infinite-length programs
he also means to ignore them.)

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

Presumable "there are no UTM's" was not the point you were
trying to make...

>>David C. Ullrich
>
>-- 
>-William "Billy" Tanksley



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)