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
>program
> > 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.
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Thu Jun 08 2006 - 03:37:21 PDT