Re: The Modified Halting Problem, Take ??? .

R. Srinivasan wrote:
Stephen Harris wrote:

If your interpretation is correct, and you can show me that they have
used this rule to support **your** statement then I will agree with
you. It is time for you to quit hand-waving and provide evidence to
support your statement:

"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."

Show me some classical logician who states this in print;
that a Turing machine can compute all the digits of Pi
and I don't mean something vague that you have to grind
through your reasoning again, or repeat yourself.


You have confused the meaning of "any". I agree that it is confusing
because of the various connotations of the English language. What I am
saying is:

For any x (x is a digit of Pi and x has been computed) <=> For all x (x
is a digit of Pi and x has been computed).


This is what I have not seen in print, and also it makes no sense to
me for you to use it to support your argument. This statement makes
sense to me if you change "has been computed" to "is computable" in
both instances. This statement sounds circular to me, not a basis
to justify a conclusion. During the computation, after each cycle,
a digit of Pi is incremented to the previous sequence; that particular
computation is ended but it says nothing about the computation of Pi
as having ended. It does mean that any finite value of x can be
computed when it is specified. I don't see how your last statement
justifies this conclusion at all, and I am thinking for myself.

>>JR: "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."
>>

What you write is not the same as saying all digits can be computed.

I am not saying that if *some* digit of Pi has been computed, then all
digits of Pi have been computed.That would amount to confusing the
existential and universal quantifiers. There is a difference between
"any" and "some". "Some digit of Pi has been computed" would be
logically like:

There exists x (x is a digit of Pi and x has been computed).

This is certainly not equivalent to "All digits of Pi have been
computed".



The NAFL model of computation however, rejects
the claim that an infinite computation, like that of Pi, can proceed
one at a time and get "completed", in the sense that "all" digits of Pi
are computed.

That is what I am objecting to. I have never seen classical logic make
the claim the the computation of Pi is completed, but only individual
digits which build up the sequence are completed. The words to describe
this are "ongoing" "unending" etc. The exact opposite of "completed".

The process of calculating the individual digits is exactly the same
as for a finite number; each individual digit is calculated and then
the turing machine moves on to calculate the next digit, it uses the
same process along the way and since it is finitely specified to a
a given degree of precision, therefore the computation will complete,
or stop. With an infinite number the same process is used, but there
is no completion to the process after each digit in the sequence is
calculated. It just keeps going on an on to the next digit in the
process, like the Easter Bunny.

You are the only one who is making a claim that the computation is
completed for Pi. You claim that this is the position of classical
logicists; I have never read it and I've read many papers on this.
You are the first educated person who has ever made such a claim.
You are making a false position of classical logic and then attacking
it, a combination of a red herring and strawman fallacy.

I do not believe there is any such claim except for your claim which
misrepresents the claims of classical logic.


All right. Let me try to highlight to you once again the point I am
trying to make. I am claiming that a non-halting TM that spits out one
digit of Pi at a time computes Pi according to the classcial model of
computation. Let us drop the discussion on whether the computation is
considered "completed" or "potential" -- this is not really a logical
issue because as noted, there is no time in the classical TM universe.

OK.

I will concentrate on trying to point out to you the paradoxical nature
of the classical claim. Instead of a single TM spitting out the digits
of Pi one at a time on a single tape, consider what I claim to be an
*entirely* equivalent setting: We have infinitely many halting TMs,
each successively (in time) computing the rational approximations 3,
3.1, 3.14, 3.141, ...... So now there are infinitely many tapes, and
first you see 3 on the first tape, then you see 3.1 on the second tape,
then you see 3.14 on the third tape, etc. Do you agree that this is
*identical* to the process of seeing 3, 3.1, 3.14, ......successively
on a single tape? I.e., do you agree that both settings perform exactly
the same operations?

Pretty close. There are an infinite number of TMs which can be placed
in one to one correspondence with the natural numbers. But the result
is not on the *same* tape. I think at this point it takes a Universal
Turing Machine to perform each of the individual procedures and get
the result on one tape. I will read on.

If so, let us proceed. The infinite set of halting
TMs does not include one that computes Pi. So there should not be any
claim that this infinite set has computed Pi. Are we in agreement?

Yes, there is no end to infinity and no last TM to correspond with
a last natural number corresponding to the end (last digit) of Pi.
In
fact Pi is not in the set because each of the infinitely many TMs
leaves out infinitely many digits of Pi. So :Pi has not been computed.

That is because each of the TMs only contains a finite number of digits.
Containing an infinte number of finite numbers is not the same as having
one set with an infinite membership of numbers.

But exactly the same operations have been performed by both settings.
So how is it that the first TM is said to compute Pi, while the second
does not? Again, forget the "potential" versus "completed" issue -- let

Both cases leave out infinitely many values. The TM that only computes
10 digits of Pi, is not different than the UTM which is instructed
to only compute 10 digits of Pi in terms of the output.

There are countably infinite Turing machines (meaning exactly TMs
and not UTMs). A UTM can simulate any and all, each and every, of
the infinite collective of TMs. They both compute Pi. Computing Pi
does not mean some end is reached. It just means that there is a
computable process available. Because there are an infinite number
of individual TMs with portions of Pi does not mean Pi has been
computed as in an end has been reached. Both situations process
computable input which is the meaning of performing a computation.
Performing a computation doesn't mean the entire computation is
finished because steps in the computation have been completed.
Neither of your cases has finished the computation of Pi. Both
of your cases have finished steps, or a subset of the computations
needed to compute Pi. Pi is computed as an ongoing process, not
computed as in the sense as being over and done with for all of
Pi. In the sense of partial computations along the way both
scenarios have finished computations or have computed some
number of digits in the expansion of Pi. The two cases are
not understood to my knowledge to be qualitatively different
and are not quantitatively different in terms of producing
tapes or a tape with a less than infinite number of actual marks.

us say the non-halting TM "potentially" computes Pi if you wish. The
infinite set of halting TMs does not even "potentially"compute Pi.


They potentially compute Pi exactly the same way. They approximate
Pi to an endless degree or to whatever finite degree is specified.

Here is the point. Each member of the set of halting TMs leaves out
infinitely many digits of Pi, i.e.,


Both cases leave out infinitely many digits of Pi.

(For each TM) (There exist infinitely many digits of Pi) such that
these infinitely many digits have not been computed.

But it would be logically wrong to interchange the quantifiers in the
above statement and conclude:

(There exist infinitely many digits of Pi) such that (For each TM)
these infinitely many digits have not been computed.

Again "each", "any", or "all" are logically the same and represent the
universal quantification.

In fact every digit of Pi does get computed in the second setting of
infintely many halting TMs. Yet each of these TMs leaves out infintely
many digits of Pi and therefore, Pi has not been computed! But the
entirely equivalent first setting of a single non-halting TM somehow
does manage to compute Pi. This should illustrate to you the danger of
representing the computation as a time-dependent, one-digit-at-a-time
process. The two settings are entirely equivalent in this case and the
paradox results. In fact the non-halting TM can claim to compute Pi
only "after" infinitely many digits of Pi have been recorded on the
tape. But this is what you reject and NAFL also rejects (NAFL refuses
to accept that infinitely many digits can ever be written down by
proceeding one digit at a time).

Computed just means that some computable input has been processed.
In a finite case when the termination is reached the computation
is over. It has been computed. But if you say Pi or any other
infinite number is computed on a UTM then you mean it is *being*
computed. In both your cases finite individual values of Pi are
computed, there is a termination; but on the UTM that one
computation is part of a larger sequence of computations and
that computation is not finished with either of your scenarios.

There is a TM to compute 3.14159 and a UTM that computes 3.14159
and in both cases the computation terminates. In the case of
the finintely specified TM there is no more process. In the case
of the UTM the production of the "9" in 3.14159 had a finitely
determined output, but the entire process is not terminated.
The entire process (all of Pi) has not been computed. Individual
finite determinations in either of your cases are computed, they
terminate. The TM has finished its overall process. The UTM has
just finished one finite step of many, each corresponding to the
value that an individual TM will produce when so specified, but
the entire process has not finished. When you say an infinite
number of TMs which compute different finite values of Pi which
could be combined to produce a larger value, there is no end
of those infinite TMs either, like any other infinity. Speaking
of a collective of all the infinite Pi computing TMs as an
entity which somehow holds the value of an infinite Pi, requires
the Cantorian notion of a completed infinity. I've have not read
of that notion being implemented in the discussion of (U)TMs.
It seems to me you are assuming or arguing that this is the case.
Perhaps this interpretation will be adjudicated by an expert.

Regards,
Stephen


.

Relevant Pages

  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... down or erasing binary digits one-at-a-time in the cells on a linear ...
    (sci.logic)
  • Re: Turing Machines and Physical Computation
    ... > So it must be bigger than any such size, and a tape ... an infinite tape is a TM that never halts due to undecidability. ... a finite number of digits. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... > So it must be bigger than any such size, and a tape ... an infinite tape is a TM that never halts due to undecidability. ... a finite number of digits. ...
    (sci.math)
  • Re: The Modified Halting Problem, Take ??? .
    ... What you write is not the same as saying all digits can be computed. ... With an infinite number the same process is used, ... We have infinitely many halting TMs, ... first you see 3 on the first tape, then you see 3.1 on the second tape, ...
    (sci.logic)
  • Re: abundance of irrationals!)
    ... >> aeo6 Tony Orlow wrote: ... >>> You claim an infinite set ... >> unlimited number of nonzero digits, do you think that if you ...
    (sci.math)