|
|
On Oct 28, 5:09 am, Stephen Harris <cyberguard-1...@xxxxxxxxx> wrote:
> R. Srinivasan wrote:
> > Aatu Koskensilta wrote:
> >> R. Srinivasan wrote:
> >>> Note that in nonstandard analysis, Nelson's "idealization principle"
> >>> goes something like
>
> >>> (For all standard x) (There exists y) y > x <=> (There exists y) (For
> >>> all standard x) y > x.
>
> >>> Here the y on the right hand side is a non-standard object (integer,
> >>> real number, etc.). Of course even non-standard analysis rejects the
> >>> inference in the form with "standard" removed from the above formula.
> >>> But still, look at the intuition behind this assertion. The above
> >>> equivalence tells us that if the TM computes the digits of Pi
> >>> corresponding to every "standard" position for cells on the tape, there
> >>> could still be infinitely many cells at "nonstandard" positions that
> >>> will not be accessed by the TM.
> >> There are no non-standard positions on the tape of an ordinary TM.
>
> > Yes of course. And there are no non-standard integers at all as far as
> > NAFL is concerned.
>
> >>> Forget the "standard" and "nonstandard"
> >>> terminologies and ask yourself, what exactly is the logical intuition
> >>> that allows for such a result? This basically seems to be saying that
> >>> if every finite integer is exceeded by some integer, then all finite
> >>> integers are exceeded by some integer, where we use "finite" in the
> >>> intuitive ("external") sense.
> >> Well, I certainly lack any such intuition.
>
> >>> This is precisely why I believe that the "one-digit-at-a-time"
> >>> computability
> >>> of Pi by a non-halting TM is at the very least paradoxical.
> >> If you say so. I'm afraid I can't really understand what you're after
> >> with all these non-standard integers and mappings. I wish you good luck
> >> in your endeavours nevertheless.
>
> > To put it in a nutshell:
>
> > (1) If you want to consider one-at-a-time counting process as
> > "completable", non-standard analysis tells us that you will necessarily
> > end up at non-standard (infinitley large) integers after exhausting the
> > standard integers. This is not acceptable in NAFL and there are no
> > non-standard integers in NAFL.
>
> > (2) The second example seems to illustrate that the one-at-a-time
> > counting process is not completable and is an ill-defined process even
> > within the naturals. This is what NAFL accepts. Therefore NAFL needs a
> > different model of computation from the classical one and I have made a
> > start in this direction.
>
> > Regards, RS
> The first example is not considered "completeable" by other people
> either. Apparently you think some people make this claim. Both
> cases are considered equivalent to each other. When you posit many
> infinite TMs, they take the same non-existent time to complete
> as a UTM which simulates the results of the many infinite TMs.
> They both use incremental steps which complete, but the entire
> process of computing Pi is never completed in either case.
Actually the two case I was referring to here were in my previous post
replying to AK. Basically what I was saying in (1) above is concerning
nonstandard arithmetic, where if you have somehow counted through "all"
standard integers, you have necessarily counted at least up to some
nonstandard integer. The second case was regarding an induction
argument by which we conclude that the counting process is not
completable even within the natural numbers, but we cannot specify
constructively which natural numbers will remain uncounted. All we can
say is that any counting process (which must be viewed in NAFL as
occurring in the human mind) will always leave out infinitely many
natural numbers; we humans cannot count through the natural numbers,
although it is not possible to say precisely where we have to give up.
> Your beef apparently is with the Successor axiom, and your
> NAFL will have the equivalent because it is an attribute of the
> human with time having a preferred direction in a causal chain
> of events. UTMs can be assigned a natural number to "label"
> each TM that corresponds to a particular digit value of Pi as
> it is computed, and both are countably infinite.
> You haven't presented any case why counting with natural numbers
> is inadequate or that a UTM becomes choked as it searches for
> new digits of the infinite expansion of Pi. I think you are
> introducing a non-existent element of time into your conception
> of completion which does not exist for a Turing machine.
The beef is not with the Successor axiom. The natural numbers are not
created by a counting process. The Successor function really applies
simultaneously to all natural numbers. The infinitely many natural
numbers exist "simultaneously" via a proof in say, Peano Arithmetic. A
counting process is separate from this. The semantics of NAFL theories
is necessarily linked to the human mind. A counting process may be
thought of as being carried out in the human mind, and "time" is
unavoidably associated with it. When we utter "one", we have in mind
the number "one" and no other natural numbers -- this process continues
with successive numbers. So it is not possible to dissociate "time"
from a counting process in NAFL. The whole purpose of this argument was
to show that one canot view a TM as outputting one digit at a time and
somehow completing its talk -- as you say, there is no such thing as
"time" in the TM universe. So all steps in the computation of Pi, for
example, can only be viewed as "completed" since, there is no such
thing as time.
>There
> is *no* infinite task that can of course not be completed unless
> the task is done for an infinite time. No such concept because
> there is no completion of computing Pi. No idea that because
> individual digits of Pi are incremented, that this process
> reaches closer to the end of Pi approaching closer and closer
> to a final end limit. You appear to think that NAFL corrects
> some misunderstanding of computability. It is already the
> case that the computation of an infinite computable number
> does not terminate although finding one digit of Pi ends
> before the algorithmic/computational proceeds to find the
> next digit in an unending string of digits to be computed.
>
> In neither case you provided is Pi considered to "have been
> computed" in a sense of total completion, although individual
> digits of Pi "have been computed". There is no logical
> inference that one meaning implies the other.
OK. I suggest that the esteemed and learned posters to this newsgroup
air their views on this.
>
> RS: "Logically (I am talking about classical logic here) if
> *any* digit of Pi has been computed, *all* digits of Pi
> have been computed. ...Ask a logician."
>
> I haven't seen any logician agree with this. Maybe because
> what you meant has very little to do with the meaning of
> what you wrote.
>
Well, since you have yourself said that there is no such thing as time
in the TM universe, I don't see how you can even give meaning to
"computed" or "will be computed", except that we humans must
necessarily view the computation process as occurring in time. What I
meant was that classically, given any digit of Pi, we can view that as
computed after a certain number of steps by the TM (or UTM). Logically,
"all" digits of Pi are to be viewed as computed in this sense, since
the argument applies to any given digit of Pi. It is this process of
"completion", that I was talking about. In NAFL, time does enter the
picture and it is necessary to reject this view of "completion after an
infinite amount of time" -- for various logical reasons, a different
model of computation is needed in NAFL. Let me clarify that I have not
claimed to find any contradiction in classical computability theory. It
is just that the process of computation seems completely abstract and
removed from reality in classical logic.
Regards, RS
|
|