Re: Computable functions/reals.

On Fri, 22 Aug 2008 10:48:51 -0700 (PDT), reasterly@xxxxxxxxx wrote:

On Aug 22, 3:15 am, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Fri, 22 Aug 2008 02:03:49 -0700 (PDT), reaste...@xxxxxxxxx wrote:
On Aug 21, 6:38 pm, MoeBlee <jazzm...@xxxxxxxxxxx> wrote:
On Aug 21, 4:19 pm, reaste...@xxxxxxxxx wrote:

BTW, Wikipedia says quite the opposite: among the Examples, they put
"The entire set of natural numbers is computable."

I prove this is incorrect.

You said that the set of natural number is not recursive. That is not
correct. You should be able to see that easily. So if 'computable' is
defined as 'recursive' (which is equivalent to 'Turing-computable'),
then the set of natural numbers is computable.

Or is your "proof' acheived by using a DIFFERENT defintion of
'recursive' and 'computable'? If so, you would do better to use, for
your notion, a different word from 'recursive' or 'computable'.

I am using the standard definition of decidable.

A set of natural numbers is called recursive,
computable or decidable if there is an algorithm
which terminates after a finite amount of time and
correctly decides whether or not a given number
belongs to the set.
http://en.wikipedia.org/wiki/Recursive_set

Say I have an infinitely long tape.
I don't really need to assume the tape is infinite,
but the proof is much simpler if I do.

Assume this tape can have no empty positions
or it has a unary representation of a natural number:
a finite string of non-blank characters followed
by a blank position.



No Turing machine can stop and say this tape
does not have a natural number on it.

As I suspected, the two of you have simply
been talking about different problems.
Typically when one says that a set of
natural numbers E is computable one means
that it is a computable subset of N. That
is, there is a machine such that if the machine
is given a natural number n the machine
determines whether or not n is in E.
The natural numbers are certainly a
computable subset of N in this sense.

If you assume the input is always a natural
number then the natural numbers are computable.
All you need is a TM that always returns "True".
You don't even need to read the input.

That's correct. And hence, by definition,
the natural numbers are a recursive set.

What you're correctly claiming is that the
natural numbers are not a computable
subset of the reals

Or, representations of natural numbers
are a subset of finite strings.

- there is no machine
which, given a real number as input, can
determine whether that real is a natural
number. This is clear.



(Assuming the Turing machine reads the tape
sequentially).

Proof:

The set of unread positions can never
be empty.

Assume that at some step, z, the set
of unread postions is empty.
z must be the largest natural number.
There is no largest natural number
therefore the set is never empty.

This proves there are (infinite) input tapes that
can't be decided in finite time or even infinite time.

So, the natural numbers are not computable.
There are inputs that can't be decided.

To show the natural numbers are not
recursively enumerable, I have to show
there are natural numbers so large
that even an infinitely fast computer
can't read them.

Here on the other hand you're back to
nonsense. If the input is given as a real number
then what you say has nothing to do with
whether the number is large or not.
Otoh if the input is a priori assumed to
be a natural number then what you say
is simply false.



_If_ we're talking about an infinitely
fast machine then the _assumption_ that
z is a natural number above is just silly.
It's true that after reading only finitely
many positions the set of unread positions
cannot be empty. It _can_ be empty
after reading infinitely many positions.

No, it can not.

I can equate reading one character from
the tape to applying the successor
function to a natural number.

You can't get infinity by applying the
successor function an infinite number
of times and you can't read an infinite
string one character at a time.

Any proof showing every natural number
is finite can be adapted to show any
string read by a sequential computer
must be finite.

But here you're still just spouting nonsense.
Any string read by an actual computer in
finite time is finite. We're not talking about
that - when we talk about Zeno machines
we're _assuming_ it can do infinitely many
things in finite time.

Russell
- 2 many 2 count

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

Relevant Pages

  • Re: Infinite Binary Strings: A Question
    ... infinite series. ... |infinite binary string would indeed determine a precise point on AB. ... to dispel the sense of counterintuitiveness about it. ... where two reals are considered ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... indexed using the reals. ... not if you can define the string of bits between uncountably distant limit ... The element 1 has an infinite ... > Without a well ordering of your index set for binary bits, ...
    (sci.math)
  • 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: Cantor Confusion
    ... So from an infinite hypothetically complete ... but that bit string will necessarily contain infinitely many ... it would be the reasoning that every finite bit string ... We can show that it works for the reals by ...
    (sci.math)
  • Re: Cantor Confusion
    ... of argument as a infinite bit patterns from .000.. ... you get a bit string that is already present in the list. ... We can show that it works for the reals by ... reasoning over a hypothetically infinite list, ...
    (sci.math)