Skip to main content
added 391 characters in body
Source Link
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.

Edit. François pointed out in the comments that you want $\varphi$ among the $T_{f(n)}$, a feature my particular example above does not have. But this is easily fixed. Let's use $T_{f(n)}(x)=x+n$ instead, and consider $\varphi(v)=v+1$, which is $T_{f(1)}$. The point, as above, is that $\varphi(v)\neq v$ and so also $T_{f(\varphi(v))}\neq T_{f(v)}$. Thus, there is no fixed point.

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.

Edit. François pointed out in the comments that you want $\varphi$ among the $T_{f(n)}$, a feature my particular example above does not have. But this is easily fixed. Let's use $T_{f(n)}(x)=x+n$ instead, and consider $\varphi(v)=v+1$, which is $T_{f(1)}$. The point, as above, is that $\varphi(v)\neq v$ and so also $T_{f(\varphi(v))}\neq T_{f(v)}$. Thus, there is no fixed point.

Source Link
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.