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

R. Srinivasan wrote:
Stephen Harris wrote:
R. Srinivasan wrote:
Stephen Harris wrote:
One thing that strikes me immediately is that "the computable set of all
Turing tapes" will not be a set or even a proper class in NAFL, snce
each tape itself is an infinite entity. But I will study the author's
argument more closely. The author's conclusions regarding Cantor's
diagonal argument and Hilbert's program are very interesting. Thanks
for this reference. I will respond to your other post tomorrow, after
studying it.

Regards, RS

I'm not quite sure why you say "each tape itself is an infinite entity"?

They're usually described as potentially infinite or finitely unbounded.

http://www.phil.cam.ac.uk/teaching_staff/Smith/godelbook/Turing.pdf

Peter Smith in the above online chapter describes it this way:

"So - admittedly at some cost in user-friendliness - we can think of our
original hand computation as essentially equivalent to following an
algorithm (a set of instructions) for doing a computation by writing
down or erasing binary digits one-at-a-time in the cells on a linear
tape, as in our diagram. The arrow-head indicates the position of the
scanned cell, i.e. the one we are examining as we are about to apply the
next computational instruction. (We'll assume, by the way, that we can
paste on more workspace as and when we need it - so, in effect, the
tape is unlimited in length in both directions)."

SH: That is a series of finite instructions, the tape grows longer and
longer in length which is a process; when you write infinite entity, I
get the impression you mean the tape is a completed infinite object
when it is meant to be an unending process or a process that just uses
as much tape as it needs to, which is not always unending. Very rarely
is the tape described as actually "infinite" in the literature. One
such error is plato.stanford.edu/entries/turing-machine however,

"A more complicated Turing machine can compute the infinite decimal
expansion of Pi."

SH: That is true because Pi is infinite. "can compute" means there is
a computable procedure which is executed one finite step at a time in
an undending series of steps; at any given time the output is finite,
and there is no last digit of Pi ever computed which one would think
of as completing the computation->(requires computable input).




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


No, it does not. There is no "all" involved ever. There are many computable numbers in which the last digit is not computed because
it is never reached. There is no "all" assumed.

>> and there is no last digit of Pi ever computed which one would think
>> of as completing the computation->(requires computable input).

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.

I think you are saying *that an infinite number can be computed in
an infinite time*. That is not induction but speculative philosophy.
I've read a few dozen webpages and papers about Pi, and I've never
seen the claim *...* that a Turing machine can discover the last
digit of Pi. I don't think you will find a reference for that on
any reputable academic website. The only educated person drawing
such an inference is you, that I know of. The logic is not well-
formed. I assume "not in a finite time" means in an infinite time?

You already mentioned time to me and I said that I only mentioned
time to say it was not involved. Show me a reference that indicates
that a Turing machine is an infinite entity, an infinite object. I suppose you could point at some sloppy and/or ignorant writing
that describes the Turing tape as an infinite tape.

A Turing machine can compute input and complete its output in a
finite number of steps (avoiding the word time) or a Turing machine
can compute an infinite number (the input procedure is still finite)
in a sequence of finite steps and in that case it will never terminate
and never compute the last digit, therefore never compute "all" digits.

Words like unending and non-terminating describe a process which is
ongoing, there is no completion, no finished product, object or entity.

Cantor invented set theory and concepts like "actualized" or completed infinities vs. potential infinities. I don't see that Turing's paper
"On computable numbers etc." needs or should be assumed to use the
concept of a completed infinity.

I don't see any reason to apply the completed infinity concept to
the Halting problem which you have done. I am now out of my depth
and there quite a few qualified to comment on this. Also I am not
enamored with Cantor's set theory so my criticism is focused on
your putting Turing under Cantor's umbrella.


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.

This part is true but I don't see a paradox because the other half
that you claim is in opposition to (conclusion is drawn by induction that the TM will write down *all* digits of Pi) isn't inducted by anybody but you that I know of. I imagine that you are thinking of
something like 'an infinite number of steps completes an infinitely
long journey'. I think this notion is itself a paradox like an
irresistible force meeting an immovable object. Immovable is used
to mean an object which resist any force. So they are both
logically and physically impossible.

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.

I think everybody else does too, including classical logic.
This smacks of red strawmen.

Hence NAFL rejects the claim that there is anything like
a "potentially" infinite tape, that is growing one step at a time
without bound and yet remains finite "forever" (whatever that means).

That is exactly what finitely unbounded means.

Since the length of the tape is an unspecified entity L that eventually
assumes "all" possible values, the tape in NAFL must be in a superposed
state of all possible lengths, which is an infinite tape. At any
particular stage of the computation, the length L may have a specific
value which the human mind asserts via a proof in some theory. Thus L
has a finite value if and only if specified by the human mind --
otherwise it is infinite in NAFL. Thus when the TM is specified with a
tape of "arbitrary" unbounded length, it is infinite in NAFL.



So you decided to throw in a dash of microcosmic quantum theory
to explain abstract concepts and devices which have no basis in macrocosmic physical reality much less non-local Oracular TMs.
I don't have any more time for this. Daryl knows far more about
it than I do so perhaps he will comment. Quite frankly, I don't
see how your papers pass peer review. One of us is certainly
insufficiently educated.

Regards,
Stephen
.

Relevant Pages

  • 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: Lambda Calculus and Turing Equivalence
    ... >>(potentially infinite) and actually infinite. ... Turing said the TM ... physical memory in the universe, if every subatomic particle could be ... It doesn't matter if you consider the tape to be only hugely finitely large. ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... >>(potentially infinite) and actually infinite. ... Turing said the TM ... physical memory in the universe, if every subatomic particle could be ... It doesn't matter if you consider the tape to be only hugely finitely large. ...
    (sci.math)
  • Re: A case for HTML as a programming language
    ... but a Turing machine without an infinite tape is not a Turing ...
    (comp.programming)
  • 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)