Hacker News Reader

Comment by petercerno | Hacker News Reader

Think about a real number with digits: 0.a_1 a_2 a_3 ... in which a_i encodes whether Turing Machine with index i (or program i) halts or not. Since Halting problem is not computable, we will never be able to compute the digits of this real number. Never in our universe.

View on HN

In the usual setting in which we do mathematics, this is a well-defined real number. That it's hard to determine its digits (even impossible when restricted to use an algorithm) is of no relevance.

However, you might be interested in the effective topos. This is an alternate mathematical universe in which one can't define construct this real number. It has a number of curious properties:

* The statement "1 + 1 = 2" is true in that topos, just like it is in the ordinary topos.

* The statement "any number is either prime or not prime" is true in that topos, just like it is in the ordinary topos, however its truth is not trivial.

* The statement "any real number is either equal to zero or not equal to zero" is false in that topos.

* The statement "any function is computable" is true in that topos (and wildly false in the standard topos).

* The statement "any function is continuous" is true in that topos (and wildly false in the standard topos).

Details are in this set of slides:

https://rawgit.com/iblech/mathezirkel-kurs/master/superturin...

Questions are welcome!

Yes but you defined the number just fine, right? "Compute" is a separate issue from "define", you can't compute a lot of things. Is this going in the intuitionistic logic direction?

Even though you defined the number, you can't really do usual stuff with it: e.g. you can't compare it to other numbers.

IMO, these kind of numbers are no more "real" than infinitesimals: https://en.wikipedia.org/wiki/Hyperreal_number

Oh it's definitely more real, as in it belongs to R and not to any of its extensions. You guys realize that the definition of R is non-controversial in modern math, right? There are fringe theories like constructivist logic and other groups that reject all infinite constructions, but this is not the consensus view among practicing mathematicians...

The way you defined that number makes it a perfectly valid element of the set R, as described by, say, the axiomatic definition here:

https://en.wikipedia.org/wiki/Real_number#Axiomatic_approach

Whether it's easy or hard or computationally intractable to compare it to other numbers, that's a totally different question unrelated to its definition.

Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not), so you can compare this number with one that's constructed by flipping its digits, or with pi, etc.

In constructive mathematics, we don't reject "all infinite constructions". The only axiom which we don't generally assume is the axiom which says "any statement is either true or not true". (Note that we also do not use the counterfactual axiom "there is a statement which is neither true nor false". In fact, we're just agnostic on some truth values.)

In constructive mathematics, there is a perfectly well-defined set of real numbers. The usual diagonalization proof that this set is not a countable set applies.

I said "and other groups that reject all infinite constructions". Some schools of thought within that general intuitionist/constructivist/etc branch of mathematical logic do reject all infinite constructions: https://en.wikipedia.org/wiki/Finitism

Either way, my point above was that this entire branch is not "mainstream math" by any means, AFAIK

I totally agree that mainstream mathematics doesn't have any problem whatsoever with infinite constructions and in fact embraces them.

I just wanted to clarify that intuitionistic and constructive mathematics don't have any problems with infinite constructions either. Finitism and ultrafinitism do, but they're not what's usually called "constructive mathematics".

There are at least three orthogonal axes which you can classify mathematical schools of thought in:

* Is the law of excluded middle accepted? ("Any statement is either true or not true.")

* Are infinite sets accepted? (They are not in finitism, but they are in constructive mathematics and of course in ordinary mathematics.)

* Can constructions implicitly refer to the result of what is being constructed? Is the powerclass of a set again a set? (Yes in ordinary mathematics and in constructive mathematics, no in predicative mathematics.)

> Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not).

Well, the fact that the number is not computable means that there will exist an index i, for which you will not be able to compute a_i (no matter how hard you try). In other words, you will not be able to analyze the Turing Machine i, i.e. it will not be possible to prove the termination or non-termination of the Turing Machine i.

So this specific digit will be a mystery forever, and you would not be able to compare it to anything.

Reply on news.ycombinator.com