0
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Feb 13 at 3:26
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also: $f(p_n) = g(n)$ where $p_i$ is the ith prime number. $\endgroup$ – Pseudonym Feb 13 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.