Re: Uncomputable Natural Numbers
reas...@gmail.com
> On Sep 4, 2:29 pm, reaste...@gmail.com wrote:
>
> > > An SC is infinitely fast if it there is no (finite) number
> > > of symbols that it cannot read in 10 minutes.
>
> > The problem with this definition is that it is provably false.
> > To begin with, I assume the input tape is long enough to
> > contain any represention of a natural number.
> > This requires me to assume the input tape is infinite.
>
> > Assume I give this infinitely fast SC an input tape with
> > all "1's" ( no blanks on the tape).
>
> > Consider the set of unread positions after each read.
> > We stop the infinitely fast SC after 10 minutes.
> > The set of unread positions is non-empty.
>
> Why? Which finite position is not read?
The infinite number of positions in the
set of unread postions, P.
This set always has an infinite number of members.
If, after read z, P_z is the empty set then we
know the tape only has z positions.
But, z is a natural number and we assumed
the tape was infinitely long.
The only way a SC can read every position
on the tape is if the tape is finite.
Even then, there exist finite tapes that
are too long to be read by any SC.
Russell
- 2 many 2 count
William Hughes
> On Sep 4, 12:21 pm, William Hughes <wpihug...@hotmail.com> wrote:
>
>
>
> > On Sep 4, 2:29 pm, reaste...@gmail.com wrote:
>
> > > > An SC is infinitely fast if it there is no (finite) number
> > > > of symbols that it cannot read in 10 minutes.
>
> > > The problem with this definition is that it is provably false.
> > > To begin with, I assume the input tape is long enough to
> > > contain any represention of a natural number.
> > > This requires me to assume the input tape is infinite.
>
> > > Assume I give this infinitely fast SC an input tape with
> > > all "1's" ( no blanks on the tape).
>
> > > Consider the set of unread positions after each read.
> > > We stop the infinitely fast SC after 10 minutes.
> > > The set of unread positions is non-empty.
>
> > Why? Which finite position is not read?
>
> The infinite number of positions in the
> set of unread postions, P.
If there are an infinite number of positions not
read name one.
- William Hughes
reas...@gmail.com
I never said the numbers were namable.
They are not namable almost by definition.
A better way of saying this is that the
representations of these numbers are
unreadable by any sequential computer.
TM's don't read natural numbers from input tapes.
They read symbols which may or may not be
the representation of a natural number.
I show the language of natural number
representations is not decidable by any SC.
No one has shown a flaw in my argument.
People have said "if an SC could read every
finite tape then your proof is wrong."
But, my proof shows no SC can determine
if the input tape is finite or infinite and
therefore no SC can halt and reject or accept
the input tapes I describe.
There exist finite representations of
natural numbers that no SC can ever read,
not even "infinitely" fast SC's.
William Hughes
> On Sep 4, 3:49 pm, William Hughes <wpihug...@hotmail.com> wrote:
>
>
>
> > On Sep 4, 6:22 pm, reaste...@gmail.com wrote:
>
> > > On Sep 4, 12:21 pm, William Hughes <wpihug...@hotmail.com> wrote:
>
> > > > On Sep 4, 2:29 pm, reaste...@gmail.com wrote:
>
> > > > > > An SC is infinitely fast if it there is no (finite) number
> > > > > > of symbols that it cannot read in 10 minutes.
>
> > > > > The problem with this definition is that it is provably false.
> > > > > To begin with, I assume the input tape is long enough to
> > > > > contain any represention of a natural number.
> > > > > This requires me to assume the input tape is infinite.
>
> > > > > Assume I give this infinitely fast SC an input tape with
> > > > > all "1's" ( no blanks on the tape).
>
> > > > > Consider the set of unread positions after each read.
> > > > > We stop the infinitely fast SC after 10 minutes.
> > > > > The set of unread positions is non-empty.
>
> > > > Why? Which finite position is not read?
>
> > > The infinite number of positions in the
> > > set of unread postions, P.
>
> > If there are an infinite number of positions not
> > read name one.
>
> I never said the numbers were namable.
> They are not namable almost by definition.
So there are natural numbers that are not namable.
Thus there must be a smallest natural number that is
not namable. Thus we have a namable natural number
n, such that n+1 is not namable.
- William Hughes
Patricia Shanahan
...
> TM's don't read natural numbers from input tapes.
> They read symbols which may or may not be
> the representation of a natural number.
> I show the language of natural number
> representations is not decidable by any SC.
This paragraph reads as though you think a TM is an SC as you have
partially defined it. That is not the case, because an SC can have
infinite non-blank input, and a TM, by definition, does not.
By all means go on defining and reasoning about your own model of
computation. Its obvious limitation, difficulty writing programs that
read unbounded length input and yet can be proved to always terminate,
seems to me to limit its usefulness, but you may be able to probe some
issues using it.
However, you cannot assume that limitations of your SC model
automatically apply to Turing machines. If you want to claim anything at
all about TMs, you should prove it starting from the normal definition
of a TM, not from however you choose to define your SC model.
Patricia
Virgil
<aee39e5b-0fd3-460a...@b30g2000prf.googlegroups.com>,
reas...@gmail.com wrote:
> But, my proof shows no SC can determine
> if the input tape is finite or infinite and
> therefore no SC can halt and reject or accept
> the input tapes I describe.
Then your SC's are not TM's.
>
> There exist finite representations of
> natural numbers that no SC can ever read,
> not even "infinitely" fast SC's.
But every one can be read by a TM.
reas...@gmail.com
> reaste...@gmail.com wrote:
>
> ...> TM's don't read natural numbers from input tapes.
> > They read symbols which may or may not be
> > the representation of a natural number.
> > I show the language of natural number
> > representations is not decidable by any SC.
>
> ...
>
> This paragraph reads as though you think a TM is an SC as you have
> partially defined it. That is not the case, because an SC can have
> infinite non-blank input, and a TM, by definition, does not.
No. A SC (or TM) can never read an infinite non-blank input.
This is what the proof shows. I don't have to assume the
input on the tape is finite. I can prove it is.
> By all means go on defining and reasoning about your own model of
> computation. Its obvious limitation, difficulty writing programs that
> read unbounded length input and yet can be proved to always terminate,
No. A SC can never halt and reject the input tape.
We have an input tape that is long enough to contain
any finite representation of a natural number.
There are only two symbols on the tape: "1" and blank.
A natural number representation is some length of "1's"
followed by a blank position.
I give you a tape. No SC (or TM) can halt and
say this tape does not have a representation
of a natural number.
I show there are always unread positions
that could be blank.
This proves the language of natural number
representations is not decidable by a SC or a TM.
This proves the SC (or TM) will never terminate
even on some finite inputs.
> seems to me to limit its usefulness, but you may be able to probe some
> issues using it.
>
> However, you cannot assume that limitations of your SC model
> automatically apply to Turing machines.
Yes, I can.
Russell
- the universe is one dimensional
ju...@diegidio.name
This is plain non sequitur.
You first say the input tape is long enough to contain any finite
representation of a natural number.
Then you say that a natural number representation is some length of
"1's" followed by a blank position.
Then, even a "finite-speed" machine halts given such an input.
> I show there are always unread positions
> that could be blank.
You show non sequitur. Isn't the *first* blank encountered enough to
end the computation? Who cares about the remaining (potential)
infinity of blanks?
-LV
> This proves the language of natural number
> representations is not decidable by a SC or a TM.
>
> This proves the SC (or TM) will never terminate
> even on some finite inputs.
>
> > seems to me to limit its usefulness, but you may be able to probe some
> > issues using it.
>
> > However, you cannot assume that limitations of your SC model
> > automatically apply to Turing machines.
>
> Yes, I can.
>
> Russell
> - the universe is one dimensional
It's man in our epoch that is monodimensional (read Marcuse).
-LV
Virgil
<e08200cd-8318-4bf7...@v16g2000prc.googlegroups.com>,
reas...@gmail.com wrote:
> On Sep 4, 6:22 pm, Patricia Shanahan <p...@acm.org> wrote:
> > reaste...@gmail.com wrote:
>
> >
> > ...> TM's don't read natural numbers from input tapes.
> > > They read symbols which may or may not be
> > > the representation of a natural number.
> > > I show the language of natural number
> > > representations is not decidable by any SC.
> >
> > ...
> >
> > This paragraph reads as though you think a TM is an SC as you have
> > partially defined it. That is not the case, because an SC can have
> > infinite non-blank input, and a TM, by definition, does not.
>
> No. A SC (or TM) can never read an infinite non-blank input.
> This is what the proof shows. I don't have to assume the
> input on the tape is finite. I can prove it is.
By what definition of "Turing Machine"?
> > By all means go on defining and reasoning about your own model of
> > computation. Its obvious limitation, difficulty writing programs that
> > read unbounded length input and yet can be proved to always terminate,
>
> No. A SC can never halt and reject the input tape.
>
> We have an input tape that is long enough to contain
> any finite representation of a natural number.
Then the tape must be infinitely long.
>
> There are only two symbols on the tape: "1" and blank.
> A natural number representation is some length of "1's"
> followed by a blank position.
>
> I give you a tape. No SC (or TM) can halt and
> say this tape does not have a representation
> of a natural number.
>
> I show there are always unread positions
> that could be blank.
You show no such thing. The TM that halts on blank never halts when
there are no blanks.
So there will not be unread positions when it does what it never does.
> > However, you cannot assume that limitations of your SC model
> > automatically apply to Turing machines.
>
> Yes, I can.
Do you also assume that the moon is made of green cheese?
reas...@gmail.com
> In article
> <e08200cd-8318-4bf7-804a-ffc53f5ad...@v16g2000prc.googlegroups.com>,
>
>
>
>
>
> reaste...@gmail.com wrote:
> > On Sep 4, 6:22 pm, Patricia Shanahan <p...@acm.org> wrote:
> > > reaste...@gmail.com wrote:
>
> > > ...> TM's don't read natural numbers from input tapes.
> > > > They read symbols which may or may not be
> > > > the representation of a natural number.
> > > > I show the language of natural number
> > > > representations is not decidable by any SC.
>
> > > ...
>
> > > This paragraph reads as though you think a TM is an SC as you have
> > > partially defined it. That is not the case, because an SC can have
> > > infinite non-blank input, and a TM, by definition, does not.
>
> > No. A SC (or TM) can never read an infinite non-blank input.
> > This is what the proof shows. I don't have to assume the
> > input on the tape is finite. I can prove it is.
>
> By what definition of "Turing Machine"?
>
> > > By all means go on defining and reasoning about your own model of
> > > computation. Its obvious limitation, difficulty writing programs that
> > > read unbounded length input and yet can be proved to always terminate,
>
> > No. A SC can never halt and reject the input tape.
>
> > We have an input tape that is long enough to contain
> > any finite representation of a natural number.
>
> Then the tape must be infinitely long.
>
The size of the input tape is unbounded.
>
> > There are only two symbols on the tape: "1" and blank.
> > A natural number representation is some length of "1's"
> > followed by a blank position.
>
> > I give you a tape. No SC (or TM) can halt and
> > say this tape does not have a representation
> > of a natural number.
>
> > I show there are always unread positions
> > that could be blank.
>
> You show no such thing. The TM that halts on blank never halts when
> there are no blanks.
>
How do we know the TM never halts?
The TM can read, at most, a finite number of positions from the tape.
If the TM reads every position on the tape then I can prove
the input tape has a finite length and is not long enough
to hold any possible finite representation. Since we assumed
the length of the input tape is unbouded, the input tape
can't have a fixed finite length.
If the tape is unbounded and can hold any finite representation,
there will always be an infinite number of unread positions
left on the tape. Any of these positions could be blank,
proving the input is a finite representation of a natural number.
Even if we assume the TM can read an infinite number
of positions, I prove there are still an infinite number
of unread positions on the tape.
Given an unbouded tape, no TM can halt and say
the input tape does not contain the representation
of a natural number.
My proof also shows why we can't say the TM
"loops forever". The best we can say is that the
TM hasn't halted yet. There will always be an
infinite number of unread postions on the tape
and any one of them could cause the TM to halt.
William Hughes
> ... A SC (or TM) can never read an infinite non-blank input.
Your putative proof of this requires natural numbers that are not
namable. Since there are no natural numbers that are not namable
your putative proof is faulty.
- William Hughes
Patricia Shanahan
> On Sep 4, 6:22 pm, Patricia Shanahan <p...@acm.org> wrote:
>> reaste...@gmail.com wrote:
>
>> ...> TM's don't read natural numbers from input tapes.
>>> They read symbols which may or may not be
>>> the representation of a natural number.
>>> I show the language of natural number
>>> representations is not decidable by any SC.
>> ...
>>
>> This paragraph reads as though you think a TM is an SC as you have
>> partially defined it. That is not the case, because an SC can have
>> infinite non-blank input, and a TM, by definition, does not.
>
> No. A SC (or TM) can never read an infinite non-blank input.
However, the difference in *why* each of them cannot read an infinite
non-blank input is profound. By definition, a TM with infinite non-blank
input simply does not exist. An SC with infinite non-blank input can
exist, because you are defining SC and you say so. Whether an SC can
read infinite non-blank input depends on how you define SC capabilities.
For example, does it operate in time steps with a non-zero minimum duration?
...
>> However, you cannot assume that limitations of your SC model
>> automatically apply to Turing machines.
>
> Yes, I can.
I'll restate that. You obviously *can* assume anything you like. It is
more a matter of whether people will believe things you claim to prove
using that assumption. I know I won't, unless I have evidence, such as a
proof working from the TM definition, that does not depend on that
assumption.
Obviously, TM and SC are significantly different. You have already
written about a very important language, the natural numbers in unary
notation, that is TM-decidable but not SC-decidable. That implies that
even after you finish defining your SC model you will not be able to
prove it is TM-equivalent.
Patricia
reas...@gmail.com
> Obviously, TM and SC are significantly different.
TM is a subset of SC.
> You have already
> written about a very important language, the natural numbers in unary
> notation, that is TM-decidable but not SC-decidable.
My proof shows the language of natural number representations is not
TM decidable.
Patricia Shanahan
>> You have already
>> written about a very important language, the natural numbers in unary
>> notation, that is TM-decidable but not SC-decidable.
>
> My proof shows the language of natural number representations is not
> TM decidable.
You have not shown any proof based on the actual definition of Turing
machines, and the contrary can easily be proved from that definition. To
the extent that you can prove undecidability of the natural numbers from
your SC definition, it serves only to disprove your apparent assumption
of equivalence of TM-decidability and SC-decidability.
The language of unary notation natural numbers is TM-decidable by the
following TM:
There are three states, an Initial state, an Accept state, and a Reject
state.
Initial state: In all cases, rewrite the current symbol. If the current
cell contains 1, remain in state 0 and move the head right. If the
current cell contains a blank, transition to the "Accept" state. If the
current cell contains any other symbol, transition to the "Reject" state.
The Accept and Reject states are simple sinks - once it reaches one of
them, the TM remains in that state.
The initial tape, by definition, contains at most some finite number, n,
of 1 symbols. The number of steps spent in the Initial state is at most
n, and so the TM must reach Accept or Reject within a finite number of
time steps.
It reaches Accept if, and only if, the input begins with a sequence of
1's followed by a blank - that is, the input is a natural number in
unary notation. In all other cases, it reaches the Reject state.
David R Tribble
> The only way a SC can read every position
> on the tape is if the tape is finite.
I see. You are saying that since an SC can read only
finite numbers, then it cannot read them all.
reas...@gmail.com
> The language of unary notation natural numbers is TM-decidable by the
> following TM:
>
> There are three states, an Initial state, an Accept state, and a Reject
> state.
>
> Initial state: In all cases, rewrite the current symbol. If the current
> cell contains 1, remain in state 0 and move the head right. If the
> current cell contains a blank, transition to the "Accept" state. If the
> current cell contains any other symbol, transition to the "Reject" state.
>
> The Accept and Reject states are simple sinks - once it reaches one of
> them, the TM remains in that state.
>
> The initial tape, by definition, contains at most some finite number, n,
> of 1 symbols. The number of steps spent in the Initial state is at most
> n, and so the TM must reach Accept or Reject within a finite number of
> time steps.
>
> It reaches Accept if, and only if, the input begins with a sequence of
> 1's followed by a blank - that is, the input is a natural number in
> unary notation. In all other cases, it reaches the Reject state.
This TM can not decide whether an arbitrary tape has a finite unary
representation of a natural number.
Assume I give you a tape long enough to hold any unary
representation of a natural number.
You give my tape to your TM. Your TM doesn't halt after 10^googol
reads.
Can you now say the TM will never halt? No.
Can you say my tape doesn't contain a unary represetation? No.
There are still an infinite number of unread positions on the tape
and
any one of them could be a blank position.
Assume you use a Zeno machine. The first read
takes 1/2 second, the next 1/4 second, etc.
We know this ZM will preform an "infinite" number of
reads in one second.
You give my tape to the ZM and wait one second.
The ZM still hasn't halted. Can you assume the ZM
will never halt? No.
Can you assume the input tape does not have a
unary representation? No.
You halt the ZM and find the ZM has read an unimaginably
huge, but finite, number of positions. There are still an
infinite number of positions the ZM has not read and
any one of these positions could be blank.
No TM, not even an "infinitely fast" TM, can decide
the language of unary representations.
Patricia Shanahan
> On Sep 5, 9:08 am, Patricia Shanahan <p...@acm.org> wrote:
>> reaste...@gmail.com wrote:
>>> On Sep 5, 5:48 am, Patricia Shanahan <p...@acm.org> wrote:
>> ...
>
>> The language of unary notation natural numbers is TM-decidable by the
>> following TM:
>>
>> There are three states, an Initial state, an Accept state, and a Reject
>> state.
>> It reaches Accept if, and only if, the input begins with a sequence of
>> 1's followed by a blank - that is, the input is a natural number in
>> unary notation. In all other cases, it reaches the Reject state.
>
>
> This TM can not decide whether an arbitrary tape has a finite unary
> representation of a natural number.
>
> Assume I give you a tape long enough to hold any unary
> representation of a natural number.
> You give my tape to the ZM and wait one second.
> The ZM still hasn't halted. Can you assume the ZM
> will never halt? No.
> Can you assume the input tape does not have a
> unary representation? No.
>
> You halt the ZM and find the ZM has read an unimaginably
> huge, but finite, number of positions. There are still an
> infinite number of positions the ZM has not read and
> any one of these positions could be blank.
The only situation in which my TM halts is when it reaches Accept or
Reject, and at that point it has decided whether the input is the unary
representation of a natural number.
Remember, it is a TM, not an SC. Regardless of how long the tape is, the
initial string of "1" symbols is finite. My TM only looks at that string
and one immediately following tape cell. I know it will reach one of its
halting states, having made its decision, without any external
intervention or time limit. I can afford to wait.
Incidentally, it would be really helpful if you would give a full
definition for your SC model. Assuming it is intended to be similar to a
Turing machine, you could start from a TM definition and list the
differences. It is clear that the rule that a TM does not have infinite
non-blank input on its tape is not part of the SC definition. Is that
the only difference?
Patricia
scattered
> > automatically apply to Turing machines.
>
> Yes, I can.
>
Huh?
How does that differ from the following line of reasoning:
Multiplication of real numbers is not commutative.
Proof:
Let A be the matrix ... and B be the matrix ... then AB differs from
BA. QED
Matrices are not real numbers. "SC"s are not Turing Machines.
-scattered
reas...@gmail.com
See below
> The only situation in which my TM halts is when it reaches Accept or
> Reject, and at that point it has decided whether the input is the unary
> representation of a natural number.
There exist unary representations that your TM will never halt on.
> Remember, it is a TM, not an SC. Regardless of how long the tape is, the
> initial string of "1" symbols is finite. My TM only looks at that string
> and one immediately following tape cell.
OK
> I know it will reach one of its
> halting states, having made its decision, without any external
> intervention or time limit. I can afford to wait.
How do you know the TM will reach a halting state?
Even if you wait forever, there will be an infinite
number of positions on the tape that haven't been read.
> Incidentally, it would be really helpful if you would give a full
> definition for your SC model. Assuming it is intended to be similar to a
> Turing machine, you could start from a TM definition and list the
> differences. It is clear that the rule that a TM does not have infinite
> non-blank input on its tape is not part of the SC definition.
If it makes you feel better, I can add the requirement that
there only be a finite number of non-blank characters on
the input tape.
> Is that
> the only difference?
A sequential computer is any computer that reads one
position at a time from the input tape.
This would include most of the definitions I have seen
for Turing machines.
David R Tribble
>> I know it will reach one of its
>> halting states, having made its decision, without any external
>> intervention or time limit. I can afford to wait.
>
Russell Easterly wrote:
> How do you know the TM will reach a halting state?
> Even if you wait forever, there will be an infinite
> number of positions on the tape that haven't been read.
After forever, all of the positions will be read.
Here's a simple program:
1. Read the current position.
2. If it was blank, halt.
3. Otherwise advance one position.
4. Go to step 1.
After forever, the program will either
1. have halted because it encountered a blank, or
2. it will have advanced to and read every position
(all positions) on the tape.
Do you have a proof of a third possibility?
Virgil
<c24461de-d67e-4323...@w24g2000prd.googlegroups.com>,
reas...@gmail.com wrote:
> On Sep 4, 11:55 pm, Virgil <Vir...@gmale.com> wrote:
> >
> > > I show there are always unread positions
> > > that could be blank.
> >
> > You show no such thing. The TM that halts on blank never halts when
> > there are no blanks.
> >
>
> How do we know the TM never halts?
The absence of the necessary condition for halting should be your first
clue.
>
> The TM can read, at most, a finite number of positions from the tape.
And cannot halt at any of them.
>
> If the TM reads every position on the tape then I can prove
> the input tape has a finite length
Not unless you assume that the TM can stop other than on a blank entry.
As long as the TM keeps going without having read all positions, you
cannot prove anything, and until it reaches a blank it must keep going.
So your proof must wait upon the end of the universe to be completed..
>
> If the tape is unbounded and can hold any finite representation,
> there will always be an infinite number of unread positions
> left on the tape. Any of these positions could be blank,
> proving the input is a finite representation of a natural number.
There is no (finite) position which will not be eventually read unless
the TM stops before reaching that position. At least with standard TM's.
>
> Even if we assume the TM can read an infinite number
> of positions, I prove there are still an infinite number
> of unread positions on the tape.
>
> Given an unbouded tape, no TM can halt and say
> the input tape does not contain the representation
> of a natural number.
Not even if the tape does contain the representation of a natural number?
You really should get your TM's from a better supplier.
Virgil
<c06ae2b3-13aa-4a67...@q26g2000prq.googlegroups.com>,
reas...@gmail.com wrote:
> On Sep 5, 5:48 am, Patricia Shanahan <p...@acm.org> wrote:
> > reaste...@gmail.com wrote:
>
> > Obviously, TM and SC are significantly different.
>
> TM is a subset of SC.
A proper subset if a subset at all.
>
> > You have already
> > written about a very important language, the natural numbers in unary
> > notation, that is TM-decidable but not SC-decidable.
>
> My proof shows the language of natural number representations is not
> TM decidable.
It does not address TM's at all.
Virgil
<76d621f0-e0c6-4fbd...@v39g2000pro.googlegroups.com>,
reas...@gmail.com wrote:
Whyever not?
What part of the tape remains unread by the ZM after 1 second?
> Can you assume the input tape does not have a
> unary representation? No.
If that ZM is as advertised, I can.
>
> You halt the ZM and find the ZM has read an unimaginably
> huge, but finite, number of positions.
After one second, your ZM will have have run out of tape, and its built
in "out of tape" tester will have turned it off to save its internal
mechanism.
Patricia Shanahan
>> Incidentally, it would be really helpful if you would give a full
>> definition for your SC model. Assuming it is intended to be similar to a
>> Turing machine, you could start from a TM definition and list the
>> differences. It is clear that the rule that a TM does not have infinite
>> non-blank input on its tape is not part of the SC definition.
>
> If it makes you feel better, I can add the requirement that
> there only be a finite number of non-blank characters on
> the input tape.
>
>> Is that
>> the only difference?
>
> A sequential computer is any computer that reads one
> position at a time from the input tape.
> This would include most of the definitions I have seen
> for Turing machines.
However, all the definitions I've seen of Turing machines are much more
specific than that. It's a bit like using the properties of ellipses to
probe the question of whether a circle is a good shape for a wheel. If
you intend to prove things about Turing machines, why not just do so,
rather than muddling the situation with a vaguely defined model of your own?
Patricia
Virgil
<ae92e2ff-ef40-4531...@w39g2000prb.googlegroups.com>,
reas...@gmail.com wrote:
If it is a proper TM, the tape will contain at least one blank in the
direction that the TM is reading.
If it is not a proper TM, then its behavior proves nothing about the
behavior of proper TMs.
> Even if you wait forever, there will be an infinite
> number of positions on the tape that haven't been read.
Name one!
>
> > Incidentally, it would be really helpful if you would give a full
> > definition for your SC model. Assuming it is intended to be similar to a
> > Turing machine, you could start from a TM definition and list the
> > differences. It is clear that the rule that a TM does not have infinite
> > non-blank input on its tape is not part of the SC definition.
>
> If it makes you feel better, I can add the requirement that
> there only be a finite number of non-blank characters on
> the input tape.
>
> > Is that
> > the only difference?
>
> A sequential computer is any computer that reads one
> position at a time from the input tape.
> This would include most of the definitions I have seen
> for Turing machines.
But would also include a lot of other machines whose behavior is
irrelevant to the working of real TMs.
Patricia Shanahan
>> Remember, it is a TM, not an SC. Regardless of how long the tape is, the
>> initial string of "1" symbols is finite. My TM only looks at that string
>> and one immediately following tape cell.
>
> OK
>
>> I know it will reach one of its
>> halting states, having made its decision, without any external
>> intervention or time limit. I can afford to wait.
>
> How do you know the TM will reach a halting state?
By mathematical induction on the length of the input string of "1" symbols.
> Even if you wait forever, there will be an infinite
> number of positions on the tape that haven't been read.
But I'll never have to wait forever, because the initial "1" string must
be of finite length. I don't care about any part of the tape other than
any initial string of "1" symbols and the first symbol that is not a
"1". That is all my TM needs to visit to know whether it has found the
unary representation of a natural number or not.
Incidentally, if the alphabet is limited to "1" and blank, the situation
is even simpler. My TM can transition unconditionally from the Initial
state to its Accept state, always halting after one step.
Patricia
galathaea
> 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.
> 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).
there are models of the natural numbers
that contain nonstandard elements
and there is no nonstandard model of arithmetic
in which addition is recursive
just pointing this out
as there are a lot of things being stated as obvious
in this thread
that aren't so obvious
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
Mike Terry
news:ae92e2ff-ef40-4531...@w39g2000prb.googlegroups.com...
We know because we can reason about the nature of the TM, and our knowledge
of the tape it has been given. Remember - we are doing Maths here, not
Physics. We don't have to actually build the TM and sit waiting for it to
finish! :-)
Regards,
Mike.
spudnik
tetration is just gone?
> and there is no nonstandard model of arithmetic
> in which addition is recursive
thus:
have you ever seen this dude ever do any numbertheory?... me,
being quite unpracticed, reserve judgement, most of the time, but
it seems very clear that this dude simply uses an algebraware box
to runthrough a Big O of data, then presumes a proof. me,
I eschew Wolframitism & the googolplex & other oracular boxes,
unless another links to it in the newsgroup,
which is certainly bad enough.
apparently the results were justified by another, but
where is the erudite commentary from the originator,
on what in Hell it is supposed to be about?
what do you, yourself, say that it means, if
that would be interesting?
> as any real physicist might know)
thus:
wake me "up," when September ends ...
ohno -- am I late for classes, again !?!
hey, PS, is your address in the BU box, or
does this list ideowise meet the category of BU research facilitation?
Cheeny has just p e r s o n a l l y launched a diversion
from his 3rdBritishInvasionSudan plan,
involving contretemps with Mother Russia and Baby Georgia;
where is the clock on the God-am Bulletin of the Atomic Scientists,
now -- a twelveth past twenty-four hundred hours?... I just saw
the current issue at the bokstore, and the feature of the issue
is bemoaning nuclear power, while the whole planet escapes
from our '50s lightwater unfailsafe paradigm, not to mention
our late-'50s program of space (at least, it was not unmanned).
so, that paper timepiece is going to be at the whim
of the two, new candidates for Imperial Vice P., or
simply 4mo'year of Trickier Dick, whether one knows it or knot:
the Harry Potter PS of American History from Rhodes Scholarship
(Oxford U. Press), insists upon an explicit doctirne of American
Imperialism
in the vain of Teddy Roosevelt. this was reprezented in the NYTimes
of yesterday, letter to editro style, bemoaning Dick's policies,
without any acknowledgemnt that it is all legal, all written
by sub rosa lawyers in exec.orders (or where ever), and
virtual VP Joe's call for US military intervention in Durfar;
Dick can now abandon that policy to the Prendergast Machine,
Cold War Trumanism etc. ad vomitorium, R&orD!
the only truly portable "machine of time" is a good watch;
every thing else is SF garbage and "spacetime" analogy.
how many rounds in your geodesic roulette, to-day, Buckywitches?
moo-ha-ha!
--ROTC, your summer vacation in the Sahara Desert ( S u d a n ) ;
presage the Draft for your middleschool class of '12 --
brought to you by Allstate (tm) and Oxford U. Press!
http://larouchepub.com/pr/2008/080813moloch_brown.html
http://larouchepub.com/hzl/2008/3535ww_miscalc.html
http://larouchepub.com/pr/2008/080812brit_soros_stooges.html
MoeBlee
> there are models of the natural numbers
> that contain nonstandard elements
There are models, with non-standard elements, of certain
axiomatizations. Is that what you mean by 'models of natural numbers'?
MoeBlee
galathaea
yeah that's what i meant
sorry for the sloppy response
but this thread has been pretty sloppy all through
and i thought it was important to make the point
though i didn't want at the time to spend much time on it
we can define the classical theory of arithmetic
(peano in first-order form is what i intend here
but the idea is a bit more general)
that defines how numbers behave
and we can see in our everyday use of numbers
that it seems to be an adequate theory
when applied to what we encounter
this thread is about things we haven't encountered
though
and the very same theory classically used
actually doesn't make some of the claims people are saying
the "reality"
(the model ontology)
may have elements that are indeed uncomputable
and listing
even in countable models
may be nonrecursive
you can tack on more axioms
but first order theories have to confront lowenheim-skolem
which
at a minimum
implies models with uncomputable elements
my point is
a lot of physical assumptions
were implicitly being used in the discussion
and i thought some might benefit from making them explicit
reas...@gmail.com
Proof:
Russell
Patricia Shanahan
...
> 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_machine#Formal_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
george
> 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.
reas...@gmail.com
> 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.
Cenny Wenner
> 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 δ: Q×Γ^\inf → Q×Γ^\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.
William Hughes
> 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
David C. Ullrich
>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".
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.)
David C. Ullrich
>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
Patricia Shanahan
> 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
Brian Chandler
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
reas...@gmail.com
> 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.)
This is the definition of a Zeno machine (ZM).
I originally devised this proof using Zeno machines,
but the proof applies to any computer that reads
the input tape sequentially.
> What do you mean by "an infinitely fast SC" that
> can only read finite strings?
The point of the proof is to show that even an
infinitely fast computer can only read a finite
number of positions from the tape.
Assume we have the Zeno machine you describe above.
The first operation takes 1/2 second, the next 1/4 second, etc.
In one second, this computer will perform an "infinite"
number of operations.
But, when we stop the ZM after one second we will find
there are still unread positions on the tape.
Since these unread positions are finite, we can
prove the ZM read only a finite number of positions.
(assuming we start at the beginning of the tape and
read sequentially).
reas...@gmail.com
> 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.
>
> 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?
There is no benefit. This is a proof that sequential computers
can never read more than a finite number of symbols,
even if we assume they can.
We don't have to assume the number of non-blank characters
on the input is finite. We can prove it must be finite if a SC can
read it.
> 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.
I think it is worse than this.
If an infinitely fast SC can only read a finite number of symbols
then there exists "longer" finite tapes that can not be read
by any SC.
There exist representations of natural numbers so large that
no sequential computer can read them.
Chris Smith
> Assume we have the Zeno machine you describe above. The first operation
> takes 1/2 second, the next 1/4 second, etc. In one second, this computer
> will perform an "infinite" number of operations.
>
> But, when we stop the ZM after one second we will find there are still
> unread positions on the tape. Since these unread positions are finite,
> we can prove the ZM read only a finite number of positions. (assuming we
> start at the beginning of the tape and read sequentially).
Which position is it that will be unread? Suppose you answer, and tell
me that position n is unread. But then I'll tell you that the symbol at
position n was obviously read at time (1 - 1/2^n), and the machine
finished reading it at time (1 - 1/2^(n+1)), which is obviously before
the one second is over. There are no unread positions; the machine has
read them all.
--
Chris Smith
reas...@gmail.com
> 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?):
A sequential computer is any computer that reads
one (or any finite number of) position from the input
tape in a single operation.
> An SC is infinitely fast if it there is no (finite) number
> of symbols that it cannot read in 10 minutes.
The problem with this definition is that it is provably false.
To begin with, I assume the input tape is long enough to
contain any represention of a natural number.
This requires me to assume the input tape is infinite.
Assume I give this infinitely fast SC an input tape with
all "1's" ( no blanks on the tape).
Consider the set of unread positions after each read.
We stop the infinitely fast SC after 10 minutes.
The set of unread positions is non-empty.
There are still an infinite number of positions that
have not been read by the SC.
Each of these positions represent a natural number
that is too large to be read by any SC.
Chris Smith
> I think it is worse than this.
> If an infinitely fast SC can only read a finite number of symbols then
> there exists "longer" finite tapes that can not be read by any SC.
>
> There exist representations of natural numbers so large that no
> sequential computer can read them.
If you allow for infinitely long representations, this is not an
interesting fact. It's obviously true -- for example, if naturals don't
include 0, I can define the representation of a natural number 'n' to be
the fractional part of the decimal representation of (1/n), which can be
infinitely long -- but you haven't given a reason to care. It's like the
old joke: "Doctor, it hurts when I do this!" "Then, don't do that."
On the other hand, supposing your tape alphabet is non-trivial (has at
least two symbols in it), such a possible representation must contain
infinitely many invalid (infinite) strings. That is an easy consequence
of the difference in cardinality. Again true, but still not terribly
interesting, unless you have some reason that it is.
--
Chris Smith
Virgil
<33bed9d0-b745-4c53...@v16g2000prc.googlegroups.com>,
reas...@gmail.com wrote:
How is
'"long enough" that even an infinitely fast SC can't read all of it'
different from
'longer than any finite tape' ?
In my vocabulary, the latter translates directly to 'infinitely long'.
Virgil
<1043927a-9f8c-4e01...@q5g2000prf.googlegroups.com>,
reas...@gmail.com wrote:
If we start with a one ended tape reading from the end position in the
direction away from that end and allow the machine to run for a full
second, which postions remain unread?
William Hughes
Nope. For every n in N, position n was read at time 1-1/2^n.
Thus for every n in N, position n was read. Since there
are no other positions all positions were read.
- William Hughes
William Hughes
Why? Which finite position is not read?
- William Hughes
Patricia Shanahan
>> 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.
>
> I think it is worse than this.
> If an infinitely fast SC can only read a finite number of symbols
> then there exists "longer" finite tapes that can not be read
> by any SC.
>
> There exist representations of natural numbers so large that
> no sequential computer can read them.
Huh? There is a qualitative difference between processing any finite
number of cells and processing an infinite number of cells. You have
not, so far, stated any restriction in the very incomplete definition of
your "sequential computer" that would prevent it from processing a
large but finite input.
Of course, it is easy to prove that a TM can read any natural number, no
matter how large, given a reasonable encoding such as unary notation.
Patricia