What are Computable Numbers? Is computability (or non-computability) some sort of technology-dependent characteristic of numbers (via e.g. Turing Machines)? What are the philosophical implications or significance of computable (and non-computable) numbers?
Add a comment
|
5 Answers
All mathematical formalizations of (intuitive) computability are known to be equivalent, in particular they are all equivalent to computability on the universal Turing machine. So technological implementation is irrelevant. The Church–Turing thesis states that this coincides in scope with what is "computable by a human being" unconstrained by limitations of time and resources. This is obviously a philosophical statement, and some disagree, albeit a small minority, but notably early intuitionists like Brouwer and Weyl, Gödel and Lucas. According to them human mind exhibits an ability to creatively "transgress" algorithmic computation, see Does Gödel's argument that minds are more powerful than computers have the inconsistency loophole? More recent intuitionists/constructivists, with the exception of Dummett, generally accept it.
Computable numbers are the real numbers for which there is an algorithm that, given desired precision, returns approximation of the number to that precision in finitely many steps. Those are the real numbers that constructivists and finitists would allow in their versions of real analysis. More broadly, extensions of this line of thought to epistemology are discussed under Do limitations on computability and computational resources have any consequences for epistemology? See also What are the "undefinable numbers" in real analysis and philosophy? for a related class of real numbers.
The main difference is that definable numbers may utilize the full strength of set theory, whereas computable numbers are confined to the resources of arithmetic. Here is an example of uncomputable but definable number. Enumerate all well-formed sentences of arithmetic by Gödel numbers, and define a real number between 0 and 1 as follows: the n-th digit in its decimal expansion is 0 if the n-th sentence is false, 1 if it is true, and 2 if n is not a Gödel number of a sentence. It is definable because the truth predicate of arithmetic is definable (in set theory, not in arithmetic), and we can even easily compute some of its digits, e.g. those that correspond to proven theorems or their negations. But it is uncomputable because there is no algorithm to decide the truth of say the Goldbach or the twin primes conjectures. It is interesting that while constructivists and intuitionists would reject existence of this number early intuitionists did accept existence of unindividuated uncomputable real numbers based on the direct intuition of "becoming" lawless sequences, see Is Aristotle's resolution of Zeno's paradoxes vindicated by motion in the intuitionistic continuum?
-
4"... guaranteed finite time." -- Would it make sense to change that to "in a finite number of steps?" Turing machines don't deal with time. If you keep it as-is, a supertask would break your definition.– user4894Commented Apr 22, 2016 at 1:57
-
3@Conifold, could you please give an example of non-computable number?(I know that pi is computable but could not come up with example of non-computable number) Commented Apr 22, 2016 at 16:06
-
2@L.M.Student Think that through. An example in terms of what? If we could give a description that is verifiable and specified the number, it would be computable, if we give a description that is unverifiable, there would be no guarantee that some other process would not converge to the same number by chance, so we could not be certain we had not accidentally given a computable number. That is the beauty of the thing: we know we can only specify countably many numbers via countably many machines running finitely long. So most of the uncountably many real numbers simply cannot be described.– user9166Commented Apr 22, 2016 at 19:57
-
3@user4894 Good point, sloppy language on my part. I had in mind something like computer "time" measured by discrete ticks of the time stamp counter, which for the Turing machine reduces to the number of execution steps.– ConifoldCommented Apr 23, 2016 at 20:57
-
3@Conifold, thank you for adding further elaboration and example. Commented Apr 24, 2016 at 0:21
The computable numbers are not technology dependent. A universal computer can simulate any finite physical system to any desired degree of accuracy. And it can simulate not just the input and the output, but also the stages intermediate between the input and output with any desired degree of accuracy:
http://www.daviddeutsch.org.uk/wp-content/ItFromQubit.pdf.
The philosophical significance of this property of the theory of computation is that it makes the laws of physics more testable. If you have a guess about how a physical system works, you can calculate its consequences with a computer by programming it appropriately. You can then compare those consequences with what actually happens.
The laws of physics say that if you can do some particular finite set of computations, and compose those computations in networks, then you can do any computation allowed by the laws of physics. If the laws of physics were different then some other set of operations might be allowed and they might have different consequences for what could be computed. For an example, see "The Beginning of Infinity" by David Deutsch, Chapter 8. So the actual laws of physics allow a restricted subset of the set of all possible abstractions. We don't currently have an explanation for why that particular subset is allowed, which is a philosophical problem.
Most simply, computable numbers -- including computable problems -- are capable of being solved by a computing device such as calculators, computers, and, well, humans if you are so inclined philosophically.
Broadly, philosophy may approach questions of metacomputability: What is a computable machine or device? Are humans computing devices/machines? What is computability?
More specifically, philosophical interest in computability takes the form of mathematical analysis. Providing rigorous definitions and defense of complex and computing devices and functions which rely on foundational matters of mathematics, such as the theory of sets.
For a richer read than mine, see Immerman's article in the Stanford Encyclopedia of Philosophy, "Computability and Complexity."
A computable number is a real number that can be calculated by an algorithm to any level of precision. Since an algorithm is just a finite sequence of instructions, it can be -- and actually is in a digital computer -- represented as a unique finite sequence of 1s and 0s, which is also the unique binary representation of a natural number. Therefore, there are at most as many computable numbers as there are algorithms. Hence, computable numbers are at most countable. Since the set of all real numbers is uncountably infinite (Cantor), there are uncountably infinitely more non-computable real numbers than computable ones.
answered Mar 29, 2017 at 9:36
-
Welcome to Philosophy.SE. This is a nice answer insofar as that it explains what computable numbers are, but might you be able to say something about their philosophical significance?– commandoCommented Mar 30, 2017 at 21:20
Although this answer may be considered "superficial," simplistic, or obvious, at least it will provide another point of view.
As I understand it, a "computable number," is a number that can be computed by a "computer".
Any physical "computer" has definite limitations. Therefore, any number lying "outside" the computer's limitations, is a non-computable number (by the given computer).
All physical computers have limitations, therefore there are non computable numbers.
One example of these, is (1)/(0) (one divided by zero).
Although most computers are now "protected" from dividing by zero, early computers would "hang for ever" (until you hit reset, or power off), if you somehow made it divide by zero.
My interpretation of their "philosophical significance" is that there are " "things" that transcend our capabilities.
-
11/0 is not a number. It's undefined, meaning it's a string of symbols that simply doesn't refer to anything. (NB that infinity is not a number either, so you can't define 1/0 as being infinity and then claim it's a number.)– EraCommented Apr 28, 2016 at 14:42