3 added 3 characters in body

When I teach computability, I usually use the following example to illustrate the point.

Let $f(n)=1$, if there are $n$ consecutive $1$s somewhere in the decimal expansion of $\pi$, and $f(n)=0$ otherwise. Is this a computable function?

Some students might try naively to compute it like this: on input $n$, start to enumerate the digits of $\pi$, and look for $n$ consecutive $1$s. If found, then output $1$. But then they realize: what if on a particular input, you have searched for 10 years, and still not found the instance? You don't seem justified in outputting $0$ quite yet, since perhaps you might find the consecutive $1$s by searching a bit more.

Nevertheless, we can prove that the function is computable as follows. Either there are arbitrarily long strings of $1$ in $\pi$ or there is a longest string of $1$s of some length $N$. In the former case, the function $f$ is the constant $1$ function, which is definitely computable. In the latter case, $f$ is the function with value $1$ for all input $n n\lt N$ and value $0$ for $n\geq N$, which for any fixed $N$ is also a computable function.

So we have proved that $f$ is computable in effect by providing an infinite list of programs and proving that one of them computes $f$, but we don't know which one exactly. Indeed, I believe it is an open question of number theory which case is the right one. In this sense, this example has a resemblence to Gerhard's examples.

2 added 72 characters in body

When I teach computability, I usually use the following example to illustrate the point.

Let $f(n)=1$, if there are $n$ consecutive $1$s somewhere in the decimal expansion of $\pi$, and $f(n)=0$ otherwise. Is this a computable function?

Some students might try naively to compute it like this: on input $n$, start to enumerate the digits of $\pi$, and look for $n$ consecutive $1$s. If found, then output $1$. But then they realize: what if on a particular input, you have searched for 10 years, and still not found the instance? You don't seem justified in outputting $0$ quite yet, since perhaps you might find the consecutive $1$s by searching a bit more.

Nevertheless, we can prove that the function is computable as follows. Either there are arbitrarily long strings of $1$ in $\pi$ or there is a longest string of $1$s of some length $N$. In the former case, the function $f$ is the constant $1$ function, which is definitely computable. In the latter case, $f$ is the function with value $1$ for all input $n So although we have proved that$f$is computable , we didn't provide a definite algorithm in effect by providing an infinite list of programs and proving that one of them computes it$f$, but we don't know which one exactly. Indeed, and I believe it is an open question in of number theory which case actually occursis the right one. In this sense, this example has a resemblence to Gerhard's examples. 1 [made Community Wiki] When I teach computability, I usually use the following example to illustrate the point. Let$f(n)=1$, if there are$n$consecutive$1$s somewhere in the decimal expansion of$\pi$, and$f(n)=0$otherwise. Is this a computable function? Some students might try naively to compute it like this: on input$n$, start to enumerate the digits of$\pi$, and look for$n$consecutive$1$s. If found, then output$1$. But then they realize: what if on a particular input, you have searched for 10 years, and still not found the instance? You don't seem justified in outputting$0$quite yet, since perhaps you might find the consecutive$1$s by searching a bit more. Nevertheless, we can prove that the function is computable as follows. Either there are arbitrarily long strings of$1$in$\pi$or there is a longest string of$1$s of some length$N$. In the former case, the function$f$is the constant$1$function, which is definitely computable. In the latter case,$f$is the function with value$1$for all input$n

So although we have proved that $f$ is computable, we didn't provide a definite algorithm that computes it, and I believe it is an open question in number theory which case actually occurs. In this sense, this example has a resemblence to Gerhard's examples.