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


Aatu Koskensilta wrote:
R. Srinivasan wrote:
If you look at Peter Smith's description again, he says that the
computation proceeds by writing down or erasing binary digits *one at a
time". You say the same thing above. This is certainly OK for a finite
computation, but paradoxical for an infinite one. Here's why. The
classical model of computation, which Peter Smith describes here,
assumes that the TM can write Pi's digits to the tape "one at a time"
and yet write down "all" digits of Pi. This seems correct in the sense
that if the TM proceeds by writing one digit at a time, it will
apparently write down any *given* digit of Pi in a finite time. So the
conclusion is drawn by induction that the TM will write down *all*
digits of Pi, though not in a finite time. But note that there are
infinitely many digits of Pi remaining to be computed after each given
digit has been written on the tape -- so paradoxically, one can also
conclude by induction that the computation will never be completed if
it proceeds one at a time, i.e., infinitely many digits of Pi will
always remain to be computed. Classically, the logic prevents us from
making this inference.

Nothing prevents us from making these trivial observations
"classically". For any digit of Pi there is a moment when it is written
on the tape, and also at every moment there are infinitely many digits
that are not written on the tape at that time - no paradox here, and no
infinite computation involved.


As I have said in a subsequent post, what is prevented by classical
logic is an interchange of the universal and existential quantifiers.
Thus, as you said:

(For every moment)(there exist infinitely many digits of Pi) such that
these digits are not written down on the tape..

But what I said is prevented by classical logic is that obtained from
interchanging quantifiers in the above assertion:

(There exist inifnitely many digits of Pi) such that (For every moment)
these digits are not written down on the tape.

It is by preventing this second (paradoxical) inference that the
computation is said to be "completed".

If there is no infinite computation (as per your assertion), it follows
that there is only a finite computation. So how can a finite
computation have anything to do with computatbility of :Pi? Or are you
saying the computation is neither finite nor infinite because it is
ongoing in time? That makes it even more slippery.

Regards, RS

.

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: 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, ... first you see 3 on the first tape, then you see 3.1 on the second tape, ... There are countably infinite Turing machines (meaning exactly TMs ...
    (sci.logic)