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



On Oct 27, 4:53 am, Aatu Koskensilta <aatu.koskensi...@xxxxxxxxx>
wrote:
R. Srinivasan wrote:
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.

Right. And the reason such an inference is prevented is because it is
not valid; (for all x)(exists infinitely many y)P(x,y) is in general not
equivalent to (exists infinitely many y)(for all x)P(x,y). Do you have
some reason to think the two claims are equivalent in this case?


Apologies to all for the triple post.

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

Imagine a counting process where I utter "zero", and then re-map what
is left of N to N. So again I utter "zero" (to which "one" has been
mapped) and repeat the procedure. So I can draw the conclusion by
induction that I will *never* utter "one" and the remaining natural
numbers, do you agree? So does that mean that there will exist
infinitely many natural numbers that will forever remain uncounted? I
am not going to tell you what these natural numbers are precisely, I am
just asking you why should the conclusion (in *non-constructive* form)
be denied? 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.

Regards, RS

.

Relevant Pages

  • Re: The Modified Halting Problem, Take ??? .
    ... logic is an interchange of the universal and existential quantifiers. ... (there exist infinitely many digits of Pi) ... Do you have some reason to think the two claims are equivalent in this case? ...
    (sci.logic)
  • Re: Power of 2 with all even digits?
    ... > digits less than 5. ... Paul Townsend ... Interchange the alphabetic elements to reply ...
    (sci.math)
Quantcast