Indeed obtaining the tape with Omega on it would be equivalent to solving
the Halting problem, but obtaining an arbitrary random noncomputable sequence
tape is as simple as hooking up a random source to your TM.
In what way is the random source not a program?
On another point, 10,000 bits of Omega would be enough to decide the
truth or otherwise of pretty much any mathematical statement of
interest to humans. See Li and Vitanyi's comment on page 218. 10,000
bits eh - just over a KB, which is not a terribly large program.
On Thu, Jun 08, 2006 at 03:36:19AM -0400, Jesse Mazer wrote:
>
> 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
>
>
>
>
--
----------------------------------------------------------------------------
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics 0425 253119 (")
UNSW SYDNEY 2052 R.Standish.domain.name.hidden
Australia http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
--~--~---------~--~----~------------~-------~--~----~
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:58:55 PDT