Uncomputable Natural Numbers

PlanetMath defines recursive set as:
http://planetmath.org/encyclopedia/RecursiveSet.html

A subset, S, of the natural numbers, N, is said to be
recursive if its characteristic function is computable.
In other words, there is an algorithm (via Turing machine
for example) that determines whether an element
is in S or not in S.

Like most definitions of recursive, this one assumes
the input, for example, a tape to a Turing machine,
contains a natural number and the TM determines
if the input is a member of the set, S.

Assuming the input is a natural number is equivalent
to assuming the set of all natural numbers, N, is recursive.

The "characteristic function" for N is a TM
that simply halts and always returns True.
The TM doesn't even have to read the input tape
since we already assume the tape contains a natural number.

What happens if we don't assume N is recursive?

I will adapt a definition for Turing machine recognizable
I found in a posting on comp.theory:

A language, L, is said to be Sequential Computer DECIDABLE
if there exists a Sequential Computer, M, which, given any
string w that is a member of L, halts and accepts w.
If w is not a member of L the TM halts and rejects w.

I define a Sequential Computer, SC, as any machine that
reads and/or writes at most a finite number of positions
from/to a tape in a single operation.

I define the language of natural number representations
to be any length string of "1's" followed by a blank
position. Any other string of characters is not a
natural number representation.

I prove this language of natural number representations
is not sequential computer decidable.

Assume we are given an input tape long enough to
contain any possible natural number representation.

For simplicity, I will assume the input tape
can be infinitely long, that a SC can perform
an infinite number of operations, and that the
SC reads the input tape sequentially from the
start of the tape one position at a time.

Assume we are given an input tape that
contains an infinite string of "1's".
Obviously, this string is not a member of L.

Not even an infinitely fast sequential computer
can halt and reject this input tape.

Proof:

For each read operation, i, performed by the SC
let P_i be the set of unread positions.

P_i can not be empty for any i.

Assume P_z is the empty set.
This means the input tape has z positions.
Since z is a natural number and we assumed
the input tape was infinitely long,
the input tape can not have finite length, z.

If P_i is never empty, the sequential computer
can never halt and reject the input tape.
There is always the possibility there is a
blank in an unread position.

This proves the language of natural number
representations is not SC decidable.

The original definition of Turing machine
recognizable allows the TM to "loop forever"
if w is not a member of L.

This proof shows why we can never say
a SC "loops forever". Even an infinitely
fast SC can only read a finite number of
positions from the inut tape.
We can never assume the SC will never halt
(assuming there is an input the SC will halt on).



Russell
- 2 many 2 count

reasterly@gmail.com wrote:
....
> I define a Sequential Computer, SC, as any machine that
> reads and/or writes at most a finite number of positions
> from/to a tape in a single operation.
....
> Assume we are given an input tape that
> contains an infinite string of "1's".
> Obviously, this string is not a member of L.
>
> Not even an infinitely fast sequential computer
> can halt and reject this input tape.

Your SC definition differs significantly from the conventional Turing
machine (TM) definition. For a TM, only the blank tape symbol can occur
infinitely often. See, for example,
http://en.wikipedia.org/wiki/Turing_...mal_definition

Since "1" can only appear a finite number of times in a TM's input, a
simple scan over a continuous sequence of "1's" must terminate.

The difficulty you note with deciding the natural numbers, or indeed
many other sets, suggests to me that the TM definition is more useful
than your SC definition.

Patricia

On Sep 3, 11:03*pm, reaste...@gmail.com wrote:
> Assuming the input is a natural number is equivalent
> to assuming the set of all natural numbers, N, is recursive.

No, it isn't. It is equivalent to assuming that the input is finite.
Pat S.'s other reply also beats you over the head with that.

A set, by itself, can't actually even be recursive (or not).
A SUBset is recursive (or not). And the superset from which the
subset has to be
drawn basically has to be infinite. Or the individual members have to
contain an infinite amount of information.

The whole paradigm presupposes the natural numbers, basically.
N as a whole is trivially recursive because the TM that just
automatically accept-halts on all inputs accepts (exactly) N.

On Sep 3, 8:54*pm, george <gree...@email.unc.edu> wrote:
> On Sep 3, 11:03*pm, reaste...@gmail.com wrote:
>
> > Assuming the input is a natural number is equivalent
> > to assuming the set of all natural numbers, N, is recursive.
>
> No, it isn't. *It is equivalent to assuming that the input is finite.
> Pat S.'s other reply also beats you over the head with that.

How does a SC or a TM decide if the input is finite?
My proof shows we can never assume the SC
nevers halts. All we can ever say is that the SC
hasn't halted yet. There is always the possibility
that an unread position contains a blank,
proving the input was finite.

> A set, by itself, can't actually even be recursive (or not).
> A SUBset is recursive (or not). * And the superset from which the
> subset has to be
> drawn basically has to be infinite. *Or the individual members have to
> contain an infinite amount of information.
>
> The whole paradigm presupposes the natural numbers, basically.
> N as a whole is trivially recursive because the TM that just
> automatically accept-halts on all inputs accepts (exactly) N.

I don't have to assume the input tape is infinitely long.
Even an infinitely fast SC can only read finite strings.
I only have to assume the input is "long enough"
that even an infinitely fast SC can't read all of it.


Russell
- 2 many 2 count

On Sep 4, 8:01 am, reaste...@gmail.com wrote:
> On Sep 3, 8:54 pm, george <gree...@email.unc.edu> wrote:
>
> > On Sep 3, 11:03 pm, reaste...@gmail.com wrote:
>
> > > Assuming the input is a natural number is equivalent
> > > to assuming the set of all natural numbers, N, is recursive.
>
> > No, it isn't. It is equivalent to assuming that the input is finite.
> > Pat S.'s other reply also beats you over the head with that.
>
> How does a SC or a TM decide if the input is finite?
> My proof shows we can never assume the SC
> nevers halts. All we can ever say is that the SC
> hasn't halted yet. There is always the possibility
> that an unread position contains a blank,
> proving the input was finite.

The definition of a TM only allows for finite, but unbounded, length
inputs, just as they only allow finite, but unbounded, alphabets and
descriptions of the machine. The tape(s) is/are typically considered
to be of infinite, or rather, unbounded length. Do note though, that,
for a TM, at any point, there's at most a finite number of non-blank
symbols and the input is not allowed to contain blank symbols. Since
these are but symbols and you can introduce and remap them as you
please, this is not a restriction. A different, but Turing equivalent,
definition would be to allow the blank symbol in the input (e.g. if we
let the blank symbol be 0 and the alphabet {0,1}), in which case we,
for instance, demand that the size of the input or similar to be given
at the start of the input.
Either definition allows us a TM to distinguish the subset 1^* from
{0,1}^*, the first which on the input tape could be seen as 1^k
blank^inf.

Your definition certainly gives a different model of computation.
What does it mean for the machine to perform an infinite number of
operations and yet, halt? Does it simply replace the transition
function with $B&D(B: Q$B!_&#(B^\inf $B"*(B Q$B!_&#(B^\inf? i.e. a primitive step "takes
into account" the entire, not necessarily finite, memory of the
machine and replaces this value with some, possibly the same, value.

>
> > A set, by itself, can't actually even be recursive (or not).
> > A SUBset is recursive (or not). And the superset from which the
> > subset has to be
> > drawn basically has to be infinite. Or the individual members have to
> > contain an infinite amount of information.
>
> > The whole paradigm presupposes the natural numbers, basically.
> > N as a whole is trivially recursive because the TM that just
> > automatically accept-halts on all inputs accepts (exactly) N.
>
> I don't have to assume the input tape is infinitely long.
> Even an infinitely fast SC can only read finite strings.
> I only have to assume the input is "long enough"
> that even an infinitely fast SC can't read all of it.
>
> Russell
> - 2 many 2 count

On Sep 4, 2:01 am, reaste...@gmail.com wrote:

> Even an infinitely fast SC can only read finite strings.

This of course depends on definition of "infinitely fast SC".
You have not definied this term.
The only sensible definition I can come up with
is:

An SC is infinitely fast if it can read an infinite number
of symbols in a finite time.

(e.g. the first symbol in 1/2 second, the second in 1/4 second etc.)

What do you mean by "an infinitely fast SC" that
can only read finite strings?

- William Hughes

On Wed, 3 Sep 2008 20:03:40 -0700 (PDT), reasterly@gmail.com wrote:

>PlanetMath defines recursive set as:
>http://planetmath.org/encyclopedia/RecursiveSet.html
>
>A subset, S, of the natural numbers, N, is said to be
>recursive if its characteristic function is computable.
>In other words, there is an algorithm (via Turing machine
>for example) that determines whether an element
>is in S or not in S.
>
>Like most definitions of recursive, this one assumes
>the input, for example, a tape to a Turing machine,
>contains a natural number and the TM determines
>if the input is a member of the set, S.
>
>Assuming the input is a natural number is equivalent
>to assuming the set of all natural numbers, N, is recursive.

No, it's not. Assuming the input is a natural number
assumes that the input is a natural number, period.

Of course by the definition above it's trivial
to show that N _is_ recursive - the machine
simply outputs "yes".

>The "characteristic function" for N is a TM
>that simply halts and always returns True.
>The TM doesn't even have to read the input tape
>since we already assume the tape contains a natural number.
>
>What happens if we don't assume N is recursive?
>
>I will adapt a definition for Turing machine recognizable
>I found in a posting on comp.theory:
>
>A language, L, is said to be Sequential Computer DECIDABLE
>if there exists a Sequential Computer, M, which, given any
>string w that is a member of L, halts and accepts w.
>If w is not a member of L the TM halts and rejects w.
>
>I define a Sequential Computer, SC, as any machine that
>reads and/or writes at most a finite number of positions
>from/to a tape in a single operation.
>
>I define the language of natural number representations
>to be any length string of "1's" followed by a blank
>position. Any other string of characters is not a
>natural number representation.
>
>I prove this language of natural number representations
>is not sequential computer decidable.
>
>Assume we are given an input tape long enough to
>contain any possible natural number representation.
>
>For simplicity, I will assume the input tape
>can be infinitely long, that a SC can perform
>an infinite number of operations, and that the
>SC reads the input tape sequentially from the
>start of the tape one position at a time.
>
>Assume we are given an input tape that
>contains an infinite string of "1's".
>Obviously, this string is not a member of L.
>
>Not even an infinitely fast sequential computer
>can halt and reject this input tape.
>
>Proof:
>
>For each read operation, i, performed by the SC
>let P_i be the set of unread positions.
>
>P_i can not be empty for any i.
>
>Assume P_z is the empty set.
>This means the input tape has z positions.
>Since z is a natural number and we assumed
>the input tape was infinitely long,
>the input tape can not have finite length, z.
>
>If P_i is never empty, the sequential computer
>can never halt and reject the input tape.
>There is always the possibility there is a
>blank in an unread position.
>
>This proves the language of natural number
>representations is not SC decidable.
>
>The original definition of Turing machine
>recognizable allows the TM to "loop forever"
>if w is not a member of L.
>
>This proof shows why we can never say
>a SC "loops forever". Even an infinitely
>fast SC can only read a finite number of
>positions from the inut tape.
>We can never assume the SC will never halt
>(assuming there is an input the SC will halt on).
>
>
>
>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.)

On Wed, 3 Sep 2008 23:01:15 -0700 (PDT), reasterly@gmail.com wrote:

>On Sep 3, 8:54*pm, george <gree...@email.unc.edu> wrote:
>> On Sep 3, 11:03*pm, reaste...@gmail.com wrote:
>>
>> > Assuming the input is a natural number is equivalent
>> > to assuming the set of all natural numbers, N, is recursive.
>>
>> No, it isn't. *It is equivalent to assuming that the input is finite.
>> Pat S.'s other reply also beats you over the head with that.
>
>How does a SC or a TM decide if the input is finite?

It doesn't. It's not required to do so.

Suppposing that S is a subset of the natural numbers,
S is recursive if there exists a TM with this property:
_If_ the input is a natural number n _then_ the
machine says "yes" or "no" depending on whether
or not n is in S.

There's no requirement whatever about what happens
if the input is not a natural number.

>My proof shows we can never assume the SC
>nevers halts. All we can ever say is that the SC
>hasn't halted yet. There is always the possibility
>that an unread position contains a blank,
>proving the input was finite.
>
>> A set, by itself, can't actually even be recursive (or not).
>> A SUBset is recursive (or not). * And the superset from which the
>> subset has to be
>> drawn basically has to be infinite. *Or the individual members have to
>> contain an infinite amount of information.
>>
>> The whole paradigm presupposes the natural numbers, basically.
>> N as a whole is trivially recursive because the TM that just
>> automatically accept-halts on all inputs accepts (exactly) N.
>
>I don't have to assume the input tape is infinitely long.
>Even an infinitely fast SC can only read finite strings.
>I only have to assume the input is "long enough"
>that even an infinitely fast SC can't read all of it.
>
>
>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.)

reasterly@gmail.com wrote:
> On Sep 3, 8:54 pm, george <gree...@email.unc.edu> wrote:
>> On Sep 3, 11:03 pm, reaste...@gmail.com wrote:
>>
>>> Assuming the input is a natural number is equivalent
>>> to assuming the set of all natural numbers, N, is recursive.
>> No, it isn't. It is equivalent to assuming that the input is finite.
>> Pat S.'s other reply also beats you over the head with that.
>
> How does a SC or a TM decide if the input is finite?
> My proof shows we can never assume the SC
> nevers halts. All we can ever say is that the SC
> hasn't halted yet. There is always the possibility
> that an unread position contains a blank,
> proving the input was finite.

For a TM, deciding whether there is infinite non-blank input is trivial.
The answer, by definition of TM, is always "false".

The problem only exists for your definition of SC. Presumably, you feel
removing the requirement that non-blank symbols only appear a finite
number of times brings some benefit. What is the benefit?

The cost is that many theorems would have to be restated in the form
"Either there is infinite non-blank input or X", where X is the theorem
as it would be stated for a TM. For example, every proof that an SC is a
decider for a language with unbounded sentence length would have to have
an exception for the infinite non-blank input case.

Patricia

William Hughes wrote:
> On Sep 4, 2:01 am, reaste...@gmail.com wrote:
>
> > Even an infinitely fast SC can only read finite strings.
>
> This of course depends on definition of "infinitely fast SC".
> You have not definied this term.
> The only sensible definition I can come up with
> is:
>
> An SC is infinitely fast if it can read an infinite number
> of symbols in a finite time.
>
> (e.g. the first symbol in 1/2 second, the second in 1/4 second etc.)
>
> What do you mean by "an infinitely fast SC" that
> can only read finite strings?

How about (what's an SC, by the way?):

An SC is infinitely fast if it there is no (finite) number
of symbols that it cannot read in 10 minutes.

This avoids the notion of "an infinite number of symbols" (which seems
to me just about as undefined as "infinitely fast").

I am, as they say in the vernacular (wherever that is), gobsmacked to
notice who is the OP.

Brian Chandler