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 email@example.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---