I was very impressed on learning that Turing proved that a turing machine could compute any computable number... but then I started to wonder how one could prove such a thing. It seemed you'd need a definition of "computable" and a definition of "turing machine" and then show its equivalence. But how could you define what was "computable", and show it was true? That's the nub of the problem and it seemed impossible to me. Eventually I read his paper, and it turns out he thought so too:
9. The extent of the computable numbers.
No attempt has yet been made to show that the “computable” numbers include all
numbers which would naturally be regarded as computable. All arguments which can be
given are bound to be, fundamentally, appeals to intuition, and for this reason
rather unsatisfactory mathematically.
Most numbers are uncomputable because most real numbers are infinite strings of non-repeating digits, which obviously would never fit in a computer. More interesting non-computable numbers include the Busy Beaver problem https://en.wikipedia.org/wiki/Busy_beaver There doesn't seem to be a way to compute these numbers without basically trying out every possible answer.
But is the universe even modeled by real numbers or is this solely a concept of the mathematical domain?
Hawking calculated the Bekenstein bound, which proved an upper bound on the amount of information that can be contained within a given volume. As black holes are maximal entropy objects, one can compute the entropy for a certain black hole volume and equate that with Shannon entropy to determine the number of bits. This suggests, to some degree, that the fundamental particle is the bit.
(This also proves that a true Turing machine with unbounded memory is not physically possible.)
This whole thing is in the "mathematical domain". The point is that you can define a number in such a way that it clearly exists, but there's no good way to calculate it.
Although it is commonly taught in undergrad classes as "stating that Turing machines and lambda calculus are equivalent" (which to be clear, it does), the premise of the Church-Turing Thesis is that all computable functions can be computed with Turing machines/lambda calculus.
The Church-Turing Thesis is unproven, but these days almost universally beleived to be true. Wikkpedia has a fairly decent coverage of all this stuff, if anyone is new to this topic.
