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

Stephen Harris wrote:
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.

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.


Who said anything about the "last" digit of a computable number? It
certainly is not my claim that Pi has a "last digit". It is not true
either in classical logic or in NAFL. Logically (I am talking about
classical logic here) if *any* digit of Pi has been computed, *all*
digits of Pi have been computed. Any=all. Ask a logician. "Any" and
"all" are expressed by putting in a *universal* quantifier in front of
the variable, i.e., "for all x" is the same as "for any x". So here is
the classical claim again -- any given digit of Pi is computed (in a
finite time, if you want to bring in time). Therefore Pi is computable
in the sense that I cannot show you a digit of Pi that cannot be
computed in a finite time. However, it is not claimed that all digits
of Pi are computed in a finite time -- that would be a logically wrong
inference, involving an interchange of a universal and existential
quantifier. Ask a logician.


>> 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?

I am still within *classical logic* here. Read again what I wrote
above.

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.


The Stanford Encyclopedia of philosophy is a "sloppy" and "ignorant"?

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.


There is no such thing as the last digit. The computation is
"completed" in the sense that I described above (any=all). Ask a
logician.

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.


Ask a logician. Your stand amounts to disagreeing with classical logic.
Any=all in logic. The induction that I claimed is paradoxical is
disallowed in classical logic because it invovles an illegal
interchange of a universal and existential quantifier. i.e., the
induction "any finite number is exceeded by some number. Therefore all
finite numbers are exceeded by some number" is disallowed in classical
logic. What about NAFL? Well, if you are talking about natural numbers,
the same rule applies, so there is no "last" natural number. The digits
of Pi are finite entities corresponding to integers (which are ordered
pairs of naturals), so there is no "last digit" of Pi in NAFL. either
-- the same rule applies. However this rule does not apply to infinite
entities like real numbers in NAFL. There is *necessarily* a +-00 in
the NAFL real line. So have I violated a fundamental rule of logic? No.
The rule does not apply because it is illegal to quantify over infinite
entities in NAFL and the real numbers are infinite classes (Cauchy
sequences of rationals). The way infinitely many real numbers are
*constructed* in NAFL ensures the if you construct every finite real
number, you have necessarily constructed +-00.

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.


And that is exactly what is rejected by NAFL.

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.

No. Not quantum theory. But quantum logic, as it is embodied by NAFL.
There is nothing *physical* involved. Quantum mechanics or any theory
is a purely logical construct in NAFL. Note that NAFL is a
non-classical logic that justifies some "weird" principles of quantum
mechanics, such as, superposition and entanglement. So it is entirely
reasonable that the logic NAFL requires some TMs to exist that follow
the principles of quantum logic, rather than classical logic. However,
I have a long way to go before actually constructing a theory of
quantum mechanics in NAFL. I have just now gotten to real analysis in
NAFL.

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.

You are making the mistake of condemning something that you fail to
understand. My work regarding NAFL has been published after peer
review. And the reviewers included quantum logicians. I will not bother
trying to explain how NAFL constructs the real numbers in any detail.
Here is the brief explanation of what I tried to get across in my
previous post. In NAFL, any super-class that includes infinitely many
TMs, each of which computes 3, 3.1, 3.14, ...., i.e., every rational
approximation of Pi, necessarily includes a non-classial TM that
computes Pi. This non-classical TM follows the principles of NAFL (or
quantum logic) and allows for the TM to access a "random" digit of Pi.
This is does not hold in classical logic or for that matter, in
standard theories of quantum computation. It is not the NAFL claim that
Pi has a last digit. Each of the rational approximations mentioned
above is a real number. The super-class of real numbers {3, 3.1, 3.14,
.....} containing every rational approximation of Pi necessarily
includes Pi in NAFL, but not in classical logic. To understand this in
any detail would require more effort from you than you are willing to
make.

Regards, RS

.

Relevant Pages

  • Re: Why? [was Re: Cantor`s powerset theorem is false?]
    ... Such a TM will have a finite input tape and a finite output tape. ... each natural number by a string of 1's followed by a blank. ... using what is essentially an infinite translation table. ... It is true that we can compute any digit of PI. ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... This non-classical TM follows the principles of NAFL (or ... Pi has a last digit. ... containing every rational approximation of Pi necessarily ... Classically, the infinite ...
    (sci.logic)
  • Re: Continuum hypothesis
    ... That makes infinite sets impredicative ... It is the NAFL truth ... You say the syntax is that of classical first order logic. ... Kronecker had to say about this. ...
    (sci.logic)
  • Re: Continuum hypothesis
    ... about formal systems with an infinite domain of discourse (e.g. the ... *quantification* over infinite entities, i.e., at some point you are ... acceptable in NAFL, which will not;permit them. ... If there exists a model for NPA (the NAFL ...
    (sci.logic)
  • 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)