World's most popular travel blog for travel bloggers.

Each finite segment of a noncomputable integer sequence is computable

, , No Comments
Problem Detail: 

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?

Asked By : mafu
Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37112

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback