# There are functions with f (n) = f (2n) which can't be calculated

I have to proofe that there are functions defined by $$f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$$, which are not-computable. However I'm not really sure about the correct method.

I thought about a proof by contradiction. Assume each of those functions are computable. Then, by the Church-turing-thesis, there has to exist a TM which can compute every of those functions. Therefore $$L(M)=\{code(M) | \text{M calculates this type of function}\}$$ would be decidable. However I profed earlier, that this language is undecidable. This would lead to a contradiction, but I'm not sure about the correctness of my profe...

Thank you for your help :)

• The condition f(n) = f(2n) allows you to define f(n) any way you like for odd n, and then the values for even n are defined. That’s not much of a restriction. Feb 13, 2020 at 3:26

Cook up some encoding of Turing machines so that if $$n$$ codes a machine, $$2 n$$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $$n$$ and $$n \cdot 2^k$$ represent the same machine). Then use that e.g. $$\operatorname{HALT}(M)$$ (does $$M$$ halt if started on an empty tape?) isn't computable.
Another way to do it: Take any non-computable function $$g(n)$$, then the function defined as:
$$\begin{equation*} f(2^k (2 n + 1)) = g(n) \end{equation*}$$
for all $$k \ge 0$$ satisfies your conditions.
• Also: $f(p_n) = g(n)$ where $p_i$ is the ith prime number. Feb 13, 2020 at 4:31