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

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 13, 2020 at 3:26

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Also: $f(p_n) = g(n)$ where $p_i$ is the ith prime number. $\endgroup$
    – Pseudonym ♦
    Commented Feb 13, 2020 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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