random

[David C. Ullrich]

On Thu, 07 Jun 2001 21:28:35 GMT, wtanksle at dolphin.openprojects.net
(William Tanksley) wrote:

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

Huh??? I _did_ explain how I reached that conclusion! And then instead
of saying "so there" I acknowledged that that was presumably not what
you meant to say. This is not "bringing ego into it", this is _saying_
that what you appear to have said is clearly not what you meant to 
say, wondering what you _did_ mean to say.

Here's how I reached that conclusion. _As_ I pointed out yesterday,
(as you _quote_ me pointing out), you _said_

(i) A UTM has to have an "indefinite number" of states - it has to
be able to count to [omega - let's call it aleph_0 instead to avoid
confusion] and that requires an infinite number of states.

(ii) A UTM has a finite number of states.

Both (i) and (ii) are things you _said_ directly above. It is 
extremely easy to deduce from (i) and (ii) that there is no
UTM: If there _were_ a UTM then it would have infinitley
many states, by (i), and it would also have finitely many
states, by (ii).

So it _does_ follow, (and it follows very easily, and I
_did_ say how it follows) from what you said that there
are no UTM's. I can't believe that you _meant_ to imply
that there are no UTM's, hence my [snipped] statement
that presumably this is not what you meant to say.

"It would have been polite to continue talking"???
You _snipped_ the "presumably this is not what you
meant". When you appear to have said that there are
no UTM's how _should_ I reply in order to be polite?

And what the heck does anything I said have to do
with "ego"?

>I think you're questioning why you'd need an infinite number of states to
>run your 'programs'. 

No, it's clear that I need infinitely much storage to be able
to emulate an arbitrary TM. This is true of _any_ UTM -
hence _any_ UTM must use the tape itself in the "emulation",
so as to be able to achieve infinitely many (external)
states.

What I was questioning was the conjunction of your two
assertions that (i) any UTM needs infinitely many states
while (ii) a UTM has only finitely many states. Looking
back at what I wrote I can't see how I could have made
it any more clear that this is what I was questioning.

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

Oh, so there's the misunderstanding. No, "writing programs" is not
computable, in the sense that there is no algorithm exlaining
how to write a program that will perform a given task. But
that's not required here; the things my UTM needs to do
are all definitely computable (by a finite-state machine
with unbounded storage space).

It _is_ easy to give a computable enumeration of all the Turing
machines. Ie it is very easy to write a function TM(n) which
returns the nth Turing machine on request. If you don't believe
that say so and I'll supply a proof. It's true - not only are
the TM's countable they are effectively countable.

[In fact it's easy to write a NextTM(T) function with this
property: If you start with an "empty" TM T_0 and then
let T_1 = NextTM(T_0), T_2 = NextTM(T_1), etc, then each
TM occurs exactly once in the sequence T_0, T_1, etc.
I added a sketch below, with Python programs in place of
TM's.)

So the semantics for my UTM is like so: Read the 0's until
you get to a 1. Say there were n zeroes. Construct the n-th
Turing machine, and then execute it.

[Or to describe it at a little lower level: Find or create
some blank space on the tape. Write a specification for
the empty TM there. Now start reading the input. Each time 
you read a 0 replace the current virtual TM with NextTM(the
current TM). When you read a 1 stop that. Now execute the
current TM.)

And now when you want to use the UTM to emulate a given
TM T you just figure out the n such that T = T_n and
then pass n 0's and a 1 to the UTM.

There are all sorts of subtleties here, I suppose. For
examnple looking at T_42 there's no way to tell what
it does. And if we have something we want to do there's
no way to say exactly what TM is going to do that, hence
no way to say what T_n we want. But all this is 
irrelevant - my UTM is not required to do a programmer's
job for him, any more than any other UTM is required to
do this. All that's required is that _given_ a TM T
there exists a program to make the UTM emulate T.
(I'm not certain whether the rules say that there
has to be a computable way to get from the TM to the
program that emulates it - I imagine so, else the
UTM would not be useful. But that's moot, because for
my UTM the program that emulates the TM T _is_
computable.)

>And /that/ is countably infinite.

Not sure exactly what set is being asserted to be infinite
here, but no, my UTM requires only finitely many (internal)
states - it also requires an infinite tape, like any
UTM does.

>>David C. Ullrich

Ok. Here's how to write a NextPythonProgram
in Python. With the property that if s is a
string representing a syntactically valid
Python program then NextPythonProgram(s)
is another string representing a valid
Python program, and if you start with
s_0 = '' and then s_1 = NextPythonProgram(s_0),
etc, then s_0, s_1, ... is an enumeration
of all the valid Python programs:

First write a function IsValidPythonProgram(s)
which returns 1 or 0 depending on whether the
string s is a syntactically valid Python program.
(Whether something is syntactically valid _is_
computable, even though it may not be computable
whether a string will terminate with a syntax
error. Eg

bad_code = 'this is not a valid program'
exec(bad_code)

_is_ a syntactically valid Python program.)

You also need a NextString function so that
if s is a string then NextString(s) is the
next string in some enumeration of finite
strings - this is easy. Now:

def NextPythonPrograms):
  next = NextString(s)
  while not IsValidPythonProgram(next):
    next = NextString(next)
  return next

And there you are. Note these are actual
real Python programs I'm talking about,
nothing abstract or hypothetical about
any of it. (The IsValidPythonProgram
would be a little complicated. But if
it's not theoretically trivial then
there would be big problems with Python,
like when the compiler can't quite make
up its mind whether some bit of code
is valid...)

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