2 ms·
Turing proved the existence of non-computable reals, so the two are not the same. Also Chaitin's constant is a non-computable real number with a precise mathema
by primodemus 15y ago
Turing proved the existence of non-computable reals, so the two are not the same. Also Chaitin's constant is a non-computable real number with a precise mathematical definition.
See: http://en.wikipedia.org/wiki/Chaitins_constant http://en.wikipedia.org/wiki/Chaitins_constant
- pygy_ 15y agoThe Curry-Howard isomorphism states (and this has been proved) that for each formal proof in math, there is a corresponding computer program that halts, and reciprocally. This means that it is possible to express the proofs of your statements in code. On the other hand, non-halting programs are AFAIK beyond the reach of formal logic, and as consequence, the set of logical proofs (or more accurately, its isomorphic twin) is a subset of the set of all computer programs.