patternModerate
To what extent is my interpretation of computable numbers correct?
Viewed 0 times
computablewhatextentnumberscorrectinterpretation
Problem
Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to calculate all of the digits of $\pi$ and begins dismembering the person. This is possible because $\pi$ is a computable number.
In contrast, if the person had asked the robot to calculate Chaitin's constant (assuming the robot didn't say something like "which Chaitin's constant?" or "insufficient parameters") or some other non-computable number, would the people have been able to escape the robot's dismembering?
As far as I understand (1)(2), the robot could make an algorithm to calculate the first $n$ digits for any $n$, but to attempt to compute "all" of Chaitin's constant would take an infinite amount of time, because each new digit would require a new program, or something like this.
Question: Is this interpretation at all correct or am I completely off the mark here? To what extent could one describe computable numbers as numbers which "prevent a robot in this specific situation from dismembering people"?
I.e., do all non-computable numbers have algorithmically random (decimal, binary, etc.) expansions?
Source.
In contrast, if the person had asked the robot to calculate Chaitin's constant (assuming the robot didn't say something like "which Chaitin's constant?" or "insufficient parameters") or some other non-computable number, would the people have been able to escape the robot's dismembering?
As far as I understand (1)(2), the robot could make an algorithm to calculate the first $n$ digits for any $n$, but to attempt to compute "all" of Chaitin's constant would take an infinite amount of time, because each new digit would require a new program, or something like this.
Question: Is this interpretation at all correct or am I completely off the mark here? To what extent could one describe computable numbers as numbers which "prevent a robot in this specific situation from dismembering people"?
I.e., do all non-computable numbers have algorithmically random (decimal, binary, etc.) expansions?
Source.
Solution
This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition.
$\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as output, and we actually need a "better" definition.
To fix this issue, we say a number $p$ is computable, if we can approximate $p$ up to any given precision. One way of formalizing this is requiring the existence of a program $M_p(n)$, which upon receiving a number $n$ outputs (in finite time) a number $\hat{p}$ such that $|\hat{p}-p|\le\frac{1}{n}$. The comic actually refers to this definition, as $\pi$ having an infinite expansion does not prevent the robot from dismembering the guy.
If your goal is to avoid dismembering, then it is not clear how to use uncomputable numbers. What exactly is the meaning of calculate $x$? If i ask for some fixed approximation of an uncomputable number, then the robot can give me one (sure, it has no way of algorithmically producing the approximation, but perhaps this is some weird robot with a table of all approximations to any natural constant up to $10^{-100}$). You would probably stand more chance with incompleteness issues, rather than with computability issues. I would ask the robot for a proof in $ZFC$ of its consistency. If it is consistent, he wont find any, and if it isn't, who wants to live anyway.
$\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as output, and we actually need a "better" definition.
To fix this issue, we say a number $p$ is computable, if we can approximate $p$ up to any given precision. One way of formalizing this is requiring the existence of a program $M_p(n)$, which upon receiving a number $n$ outputs (in finite time) a number $\hat{p}$ such that $|\hat{p}-p|\le\frac{1}{n}$. The comic actually refers to this definition, as $\pi$ having an infinite expansion does not prevent the robot from dismembering the guy.
If your goal is to avoid dismembering, then it is not clear how to use uncomputable numbers. What exactly is the meaning of calculate $x$? If i ask for some fixed approximation of an uncomputable number, then the robot can give me one (sure, it has no way of algorithmically producing the approximation, but perhaps this is some weird robot with a table of all approximations to any natural constant up to $10^{-100}$). You would probably stand more chance with incompleteness issues, rather than with computability issues. I would ask the robot for a proof in $ZFC$ of its consistency. If it is consistent, he wont find any, and if it isn't, who wants to live anyway.
Context
StackExchange Computer Science Q#73976, answer score: 11
Revisions (0)
No revisions yet.