Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)

From: Michael N. Christoff (mchristoff_at_sympatico.caREMOVETHIS)
Date: 02/17/04 

Date: Tue, 17 Feb 2004 06:04:40 -0500

"Russell Easterly" <logiclab@comcast.net> wrote in message
news:odydnXiTFf4ZQqzdRVn-ig@comcast.com...
>
> "Stephen Harris" <stephen.p.harris@sbcglobal.net> wrote in message
> news:LhXXb.13180$gP1.7891@newssvr29.news.prodigy.com...
> >
> >
> > Dave Seaman:
> > A set is recursive if there is an effective procedure (a Turing machine,
> > perhaps) that can decide membership in the set. That is, the machine
> > halts and returns 1 if the input is in the set, and the TM halts and
> > returns 0 if the input is not in the set.
>
>
> This is the definition of a decidable language at wikipedia:
> http://en.wikipedia.org/wiki/Decidable_language
>
> A decidable or recursive language is a formal language that is a recursive
> set, i.e., for which there exists an algorithm to solve the following
> decision problem: Given string w, does w belong to the language? The
> algorithm is not allowed to run into an infinite loop and has to produce a
> YES/NO answer for any input string after a finite amount of time. To
> formalize the rather vague term "algorithm", one usually employs Turing
> machines, but several other equivalent approaches are possible.
>
> This definition should say "finite number of steps" instead of "finite
> amount of time"
> I will come back to this.
>
> This is the definition of a recursively enumerable language:
> http://en.wikipedia.org/wiki/Recursively_enumerable_language
>
> Definition 1. Given string w as input, the algorithm halts and outputs YES
> if and only if w belongs to the language L. If w does not belong to the
> language L, the algorithm either runs forever, or halts and outputs NO.
>
> There is a second definition that you might want to read.
>
> Let me define a language, L, that consists of all unary representations of
> natural numbers.
> 1 = one, 11 = two, 111 = three, etc.
>
> This language is recursively enumerable. Given a string, x, there exists a
> TM that
> will halt after a finite number of steps if x is a member of L.
> This language is NOT decidable. Consider what happens if x is an infinite
> string
> of 1's. The TM will not halt after a finite number of steps.
>

You can't input an infinite string to the tape. If you could, it wouldn't
be a Turing machine.

> The set of all natural numbers is not a recursive set.
>

No natural number requires an infinite unary representation. All may be
represented using a finite number of 1s.

> Consider what happens when we talk about the set of all TM's.
> Assume we can encode the state transition table of a TM using
> a natural number. This set can not be recursive for the same
> reason that the natural numbers are not recursive. Given a
> string, i, we can not be sure that TM(i) is actually a TM
> because we can not be sure that i is actually a natural number.
>

All Turing machines can be finitely represented. There is no such thing as
a TM transition function that requires an infinite state automata for
representation.

> No set can contain every computable natural number.
>
> Proof:
> Assume a TM produces a tape with all of the natural numbers
> encoded in unary where each natural is followed by a 0 (or a blank).

This is impossible, a) a decider is limited to a finite number of steps
before halting, b) to output all integers in unary requires an inifnite
number of steps - hence, no TM can produce this output.

> Turing gives the state transition table of such a TM
> 010110111011110...
>
> I can define a three state TM that will find a natural number
> that is not on this tape:
>
> 1) Read right until there is a 0.
> 2) Read right until a second 0 is found.
> 3) Backup and write a 1 on the previous 0.
> Repeat steps (1) through (3).
>
> This TM will always produce a tape that has exactly one 0.
> This 0 will be at a finite position on the tape and the string of 1's
> that preceds this 0 represents a natural number that was not on
> the original input tape.
>

You have not at all proven this. First, how can there be a 0 at a finite
position from the start? If there is, there must a 0 to its right (in fact
an infinite number of zeros), hence step 2 will read this second zero, and
step 3 will go back and erase the 'remaining 0'. The part about the number
preceding the last 0 being an integer not on the tape makes no sense either.

> The Halting Problem is ill posed.
> There is no set that contains every TM

Sure there is : A = {<M> | M is a valid TM representation}

It is easy to check, given a data structure, whether the input is a valid TM
or not.

> just as there is no set
> that contains every computable natural number.
>

All natural numbers are computable. However, they _all_ can't be generated
in a single run of any algorithm/TM.

> Now, about the difference between "finite amount of time" vs
> "finite number of steps". There are theories of computing where
> a TM can perform an infinite number of steps in finite time.
> These are called "hypercomputers".
> http://en.wikipedia.org/wiki/Hypercomputer
>
> A non-deterministic Turing machine is an example of a hypercomputer.

No, an NTM is not a hyper-computer since any NTM can be simulated by a
standard TM. The NTM must be given additional abilities to become
super-Turing.

> Another example is an "accelerated Turing Machine". An ATM performs
> the first operation in one unit of time, the second operation is 1/2 unit
> of time, the third operation in 1/4 unit of time, etc. An ATM will perform
> an infinite number of operations after two units of time.
>
> Assume we have a computer that can perform an operation in one
> nanosecond. The language, L, that I defined above is not even
> recognizable if we expect an answer before the universe freezes over.
> We can easily compute a natural number, n, that is so large that
> our nanosecond computer will take 15 billion years to recognize
> n as a natural number. There is only a finite number of naturals
> less than or equal to n. There is an infinite number of naturals
> larger than n. Nearly all natural numbers are larger than n.
>
> So, we see that we have to assume that a TM can perform
> an infinite number of operations in finite time to even say
> that L is recursively enumerable.
>

To say that there is some natural number that a physical computer will never
be able to print out in unary is one thing, but to say that a TM (a purely
mathematical object) 'can't' print out certain natural numbers in unary in a
finite number of steps is not correct.

l8r, Mike N. Christoff

Relevant Pages

  • Re: infinity
    ... >>> Why are you assuming that there is a longest word in the language? ... >> finite, that means none are infinite, therefore S^L is not infinite either. ... > I am not assuming that there is a longest word. ... > the maximum string length, i.e. the largest finite natural number. ...
    (sci.math)
  • Re: Why does Cantor a target for cranks?
    ... Does To distinguish the between the size of the set of naturals and the size of a set of representations of the naturals, such as the binaries or the decimals? ... I distinguish them with different measure, one related to density on the real line, and the other related to combinatorial size as string length grows. ... Subsets of the reals are sets of points within the line. ... For a fixed alphabet and finite but unbounded word lengths, the set of words in a language and the set of naturals biject naturally. ...
    (sci.math)
  • Re: infinity
    ... >>> If the word length is finite, then the language is also finite. ... >>> x, being the length of the longest word in the language, and any finite ... > finite, that means none are infinite, therefore S^L is not infinite either. ... the maximum string length, i.e. the largest finite natural number. ...
    (sci.math)
  • No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... A decidable or recursive language is a formal language that is a recursive ... YES/NO answer for any input string after a finite amount of time. ... A non-deterministic Turing machine is an example of a hypercomputer. ... There is only a finite number of naturals ...
    (comp.theory)
  • Re: infinity
    ... >>> If the word length HAS AN UPPER BOUND, ... and I am not saying that a finite language is necessarily small. ... >> if the string length is strictly finite, ... Sounds infinite to me, this string elongation process, eh? ...
    (sci.math)