Russell Standish wrote:

>On Thu, Jun 08, 2006 at 04:24:51AM +0200, Quentin Anciaux wrote:
> >
> > Le Jeudi 8 Juin 2006 02:56, Russell Standish a écrit :
> > > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote:
> > > > Hi Bruno,
> > > >
> > > > what I undestand about the UD is that it generates all programs, a
> > > > program being simply a number from the set N.(1)
> > >
> > > No - halting programs are a subset of N, but there are uncountably
> > > infinite non-halting ones.
> >
> > Do you mean there exists programs which are not encodable in a finite 
>string ?
> > Is this really a "program" then ? And I see plenty of non-halting 
> > which are perfectly writeable in a few instruction.
> >
>Of course there are finite length non-halting programs. The question
>is whether infinite length input tapes are considered programs - isn't
>this as much a matter of definition than anything else?

But if the infinite string is not itself computable (if it can't be 
generated by a universal turing machine operating on some finite string, 
say), then we'd have no way to run such a program in the real world--imagine 
if the infinite string is Omega (a noncomputable number which encodes the 
answer to whether any turing machine operating on a computable input will 
halt or not), for example. Of course we can use a dovetailer-like solution 
where every time the universal turing machine reaches a digit of its input 
string it hasn't visited yet, we create two new "branches" where we simulate 
what would happen if it encountered a 1 *and* what would happen if it 
encountered a 0 on that step. If we run this branching simulation forever, 
then there must be some path that is identical to what would happen if that 
universal turing machine was fed Omega (or any other possible infinite 
string) as an input...but we can never know which path this is, at least not 
unless the laws of physics allow us to build machines which can solve the 
halting problem in a finite time.


You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at

Reply via email to