0
$\begingroup$

Wikipedia claims that "each finite segment of noncomputable sequence of integers is computable".

It continues to clarify: For any noncomputable function, "for any given value of n, [...] a trivial algorithm exists (even though it may never be known or produced by anyone)".

While I do believe this for the given example with busy beavers, I am not certain this is always correct. Is there a proof of this statement?

Improve this question
$\endgroup$
3
  • $\begingroup$ It's sort of trivial: consider a finite sequence $a_1,...,a_n$, then an algorithm that prints $a_1,...,a_n$ prints it... $\endgroup$
    – Shaull
    Jan 10, 2015 at 13:19
  • $\begingroup$ I'm probably misunderstanding this, but to me the problem is that a_n is noncomputable, yet that there still is a way to compute a_x for a fixed x. $\endgroup$
    – mafu
    Jan 10, 2015 at 13:23
  • $\begingroup$ The sequence is uncomputable, not every single number. Think of it this way: consider some concrete single number in $a_n$. This is just a number $k\in \mathbb{N}$, and there is an algorithm that prints out $k$ - just writes down its digits (we don't know which algorithm, but such an algorithm definitely exists). Same goes for fixed finite sequences. $\endgroup$
    – Shaull
    Jan 10, 2015 at 13:27

1 Answer 1

Reset to default
2
$\begingroup$

This is quite a fundamental point in computability theory, which has to do with the difference between being able to find and algorithm and knowing that an algorithm exists.

To illustrate the point, suppose I tell you that I'm thinking of a number between 1 and 10. Is there an algorithm that prints the number I'm thinking of? Of course! for every $i\in \{1,...,10\}$ there is an algorithm that prints $i$ and halts, so in particular, there is an algorithm that prints the number I'm thinkng of.

Do you know which algorithm prints the number I'm thinking of? no.

Similarly, every finite sequence can be printed by some algorithm. If you have a computable representation of that sequence, you can also find that algorithm, but if this finite sequence is given as an uncomputable function, then you cannot find the algorithm.

One classic example for this issue is the following: consider some TM $M$ and input $w$, we define the number $t$ as follows: $t=1$ if $M$ accepts $w$, and $0$ otherwise.

Is there an algorithm that prints $t$? yes - either the algorithm that prints $1$ and halts, or the algorithm that prints $0$ and halts.

Is there an algorithm that, given $M$ and $w$, computes the algorithm that prints $t$? No - as this would contradict the fact that $A_{TM}$ is undecidable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What would happen if you were to remove the upper limit on the number guessing? One would need infinitely many algorithms to answer. $\endgroup$
    – mafu
    Jan 10, 2015 at 13:52
  • $\begingroup$ It doesn't matter, there are infinitely many algorithms, so it's one of them... You don't need the algorithm to answer, you just need to prove that it exists. $\endgroup$
    – Shaull
    Jan 10, 2015 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.