- #1
Dragonfall
- 1,030
- 4
Can someone prove to me why computable numbers are not closed under the taking of suprema?
Sorry, I left the adjective "computable" implicit.CRGreathouse said:(2) seems to have serious problems (how to input a real number? how to operate on it in a finite amount of time?).
Hurkyl said:Sorry, I left the adjective "computable" implicit.
But we're not talking about "recognizing a real number". We're talking about "doing a calculation with a computable real number". To be computable presupposes we have a way to write the number a finite string of symbols, and the TM would be programmed to operate on such representations.Dragonfall said:I think CRGreathouse means that it is not possible to recognize a real number with a TM, which can only regonize finitely many symbols, and strings of finite length.
It could be stronger, but it doesn't need to be; it's a definition, and it has properties. It may be useful for some purpose, or it might not.Dragonfall said:(1) needs to be stronger. The TM must list those that are in the set, and those that aren't (say, in alternating order). It's the "recursive" vs. "recursively enumerable" thing all over again.
The Incompleteness of Computable Numbers refers to the fact that there are certain numbers that cannot be represented or computed by a computer or any algorithm. This means that there are numbers that exist but cannot be expressed or calculated using a finite set of instructions.
The Incompleteness of Computable Numbers is closely related to the concept of infinity. It shows that there are infinitely many numbers that cannot be computed or expressed, highlighting the limitations of human understanding and technology when it comes to infinity.
One example of an incomputable number is the Champernowne constant, which is a real number that contains the digits of pi in its decimal expansion. It is a number that is known to exist but cannot be computed or expressed using a finite set of instructions.
The Incompleteness of Computable Numbers has significant implications in both mathematics and computer science. It shows that there will always be unsolvable problems and limits to what can be computed or expressed using algorithms. This has sparked new research and developments in areas such as algorithmic randomness and computable analysis.
No, there is no way to overcome the Incompleteness of Computable Numbers. It is a fundamental limitation that exists in mathematics and computer science. However, advancements in technology and algorithms may allow us to approximate and work with these incomputable numbers to a certain degree.