Skip to main content
deleted 51 characters in body
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

No. Let $g$ be the constant function 1.

Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.

So $\{f_n\}$ is a computable list of all primitive recursive functions bounded by 1. By assumption $f_n$ is a list of all computable functions bounded by 1. Now

Now let $F(n)=1-f_n(n)$. Then $F$ is another computable function bounded by 1, distinct from all the $f_n$, contradictionso $F$ is not primitive recursive.

No. Let $g$ be the constant function 1.

Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.

So $\{f_n\}$ is a computable list of all primitive recursive functions bounded by 1. By assumption $f_n$ is a list of all computable functions bounded by 1. Now let $F(n)=1-f_n(n)$. Then $F$ is another computable function bounded by 1, distinct from all the $f_n$, contradiction.

No. Let $g$ be the constant function 1.

Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.

So $\{f_n\}$ is a computable list of all primitive recursive functions bounded by 1.

Now let $F(n)=1-f_n(n)$. Then $F$ is another computable function bounded by 1, distinct from all the $f_n$, so $F$ is not primitive recursive.

Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

No. Let $g$ be the constant function 1.

Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.

So $\{f_n\}$ is a computable list of all primitive recursive functions bounded by 1. By assumption $f_n$ is a list of all computable functions bounded by 1. Now let $F(n)=1-f_n(n)$. Then $F$ is another computable function bounded by 1, distinct from all the $f_n$, contradiction.