Consider the finite algorithm A, and the real number $0 Q1. Can such an algorithm and number exist? Q2. Can we construct such an A and prove there exist such a T? Q3. Can we prove or disprove that T is rational, irrational, normal, trancendental, algebraic? Q4. Can T have a closed form expression? Q5. Is it possible to prove or disprove that no finite algorithm that takes as input A, can output T to arbitrary precision?
Does this number exist?
1
$\begingroup$
algorithms
computer-science
computability
-
3What exactly do you mean by giving a real number as input to a finite algorithm? Since the sentences of the language of set theory are enumerable, there is a real number between $0$ and $1$ that has a $1$ in each binary digit corresponding to a theorem of ZFC and a $0$ everywhere else -- if you "give this number as input" to an algorithm that examines its digits one by one, you get the desired output -- but what would that mean? – 2011-04-07
-
2You can use Chaitin's constant to encode all this information, for instance. Note however that this number is necessarily noncomputable (so in particular, must be transcendental, and the answer to Q5 is no), as the halting problem (or first-order logic) is undecidable. – 2011-04-07
-
0So we know such a number exist, how can we know that for instance e/Pi does not by some magical coincidence have this property? – 2011-04-07
-
0I'm having trouble with 'exists' (I don't recognize it as a technical term here). Do you mean computable? What about $T$? DI'm guessing you intend that it 'exists'? Is it also computable? I feel like that should be part of the prerequisites to the question. – 2011-04-07
1 Answers
3
(I'm only offering hints as I presume this is homework, though it isn't tagged as such.)
A hint for Q1 and Q2: 'how many' provable theorems of ZFC can there be? What different definitions of 'a real' do you know, and do you know ways of converting back and forth between the different definitions? Once you have this, the other pieces should start to fall into place easily.
A hint for Q5: assuming you had such an algorithm, what would this imply about the provable theorems of ZFC?
Hints for Q3 and Q4: can you show a relationship between these questions and Q5?