Sequences of a computable function

175 Views Asked by At

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains arbitrarily large sequences of $0$'s" has been proved to be undecidable in PA or ZFC?

If not, is there any proof of the existence or non-existence of such a function?

Edit: Is there one which is also morally undecidable?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $G$ be a Gödel sentence (with intuitive meaning "I cannot be proved"), and take $$f(n)=\cases{0&\text{if }G\text{ has a proof with Gödel number }<n\\1&\text{otherwise}}$$

3
On

Let $G(n)$ be the Goodstein sequence with first element $n$, and take $$f(n)=\cases{0&\text{if }0 \ \text{is an element of} \ G(n) \\1&\text{otherwise.}}$$

EDIT: ZFC proves the statement $\unicode{8220}f(n)=0\text{ for all }n\unicode{8221}$ and also proves that that statement cannot be proved in PA. However, this alone might not imply that PA can't prove the weaker statement $\unicode{8220}f(1),f(2),f(3),\ldots$ contains arbitrarily long sequences of $0\text{s}\unicode{8221}.$ Since I don't know whether PA can in fact prove the latter (weaker) statement, I'm unsure whether my above answer is correct after all.