Re: when laypersons look smarter than math professors Re: a question for the anti-Cantorians

In sci.logic, ken quirici
<kquirici@xxxxxxxxx>
wrote
on 23 May 2005 07:28:10 -0700
<1116858490.058108.124030@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>:
>
> The Ghost In The Machine wrote:
>>
>> [2] All algorithms must terminate.
>>
>
> Unless of course you code an infinite loop :-)
>
> Ken
>

Heat death of the Universe. Next question? :-)

Of course you do have a point; there are algorithms:

j=0; for(int i = 0; i < n; i++) { j += i*i; } return j;

provably infinite loops:

while(1) printf("Yes, this is brain-dead\n");

and those that might give us pause:

k=0; while(n != 1) { if (n % 2==0) n/=2; else n=3*n+1; k++; } return k;

One of the more interesting issues is ordering a list of semicomputable
numbers. (I call a number "semicomputable" if it can be approximated
to any given degree of precision -- or any number of digits --
with a Turing machine using a sufficiently large amount of tape space.
A fully computable number in this context would have a finite number
of digits. There are admittedly a number of quibbles here; 1/3's
decimal expansion is infinite but its duodecimal expansion is not;
1/3 is a finite representation for a certain number in Q with an
infinite decimal expansion.)

Now postulate a UTM and an encoding scheme, and list the semicomputable
numbers in order:

UTM(1) = ...
UTM(2) = ...
UTM(3) = ...

(We ignore issues such as whether a TM requires a prepopulated tape,
and whether UTM(n) properly generates a number, freezes up, or
jiggles.)

Now construct an antidiagonal. Is the antidiagonal associated
with a UTM? Probably not, but I'm not sure there's an elegant
way to prove it; the best I can do is show it's not on this list.

If one restricts the range of a "real" function to that of the
semicomputables, I for one cannot be certain as to precisely
how many numbers there are (there are only a denumerably infinite
number of machines, though if one includes input tapes one might
get an uncountable number of run-sets -- but that's cheating
in a way since the input tapes would probably comprise all
real numbers in that case).

Fortunately, mathematicians are under no such restrictions.
If one has a list f : N -> R, then one can prove the existence
of (and approximate to any desired precision) an antidiagonal
number which is not on that list, or in the set
representing the actual range (as opposed to the specified
range -- the reals) of that list. Cantor found two methods,
in fact, only one of which depends on an antidiagonal (the
other depends on various properties of sequences and the
"continuumness" or contiguity of the reals).

--
#191, ewill3@xxxxxxxxxxxxx
It's still legal to go .sigless.
.

Relevant Pages

  • Re: Calculus XOR Probability
    ... If a quantitative set is mapped in ascending order from the naturals, ... number of reals on the line. ... to the subsequent logic that claims such a set cannot have infinite values. ... standard orderings, since sets in general don't come with little tags ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... If a quantitative set is mapped in ascending order from the naturals, with each increment in the domain, the range increases by some amount. ... Like it's the number of unit intervals, and the number of reals in the unit interval. ... You are using a form of infinite induction, making a claim for an infinite set based on all finite initial segments of it. ... don't have a definition for an arbitrary set of its "standard ordering" ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... If a quantitative set is mapped in ascending order from the naturals, with each increment in the domain, the range increases by some amount. ... you had said that the existence ... Like it's the number of unit intervals, and the number of reals in the unit interval. ... You are using a form of infinite induction, making a claim for an infinite set based on all finite initial segments of it. ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... length n as initial strings followed by the expansion of pi after the nth ... long decimal expansion followed by an infinite expansion. ... part can be as long as we like, we have an infinite sequence of initial ... dense in the reals. ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... Keep in mind that whatever system of axioms you come up with will ... proofs of uncountablility of the reals, but that is not going to happen. ... I have a hang-up, it's about infinite sequences. ... My point is that mathematical existence has nothing to do with physical ...
    (sci.math)