Prove or disprove that every function from N into itself is computable? Please s

Question

Prove or disprove that every function from N into itself is computable?

Please show all your work. Give me a STEP BY STEP answer, explaining how you came about your answer.

Explanation / Answer

For every computable function f : N ? N, there exists a computable function g : N ? N such that for every n we have f(n) = g(n). Proof: Assume, for the sake of arriving at a contradiction, that for some computable function f, for every computable function g, there exists an n such that f(n) > g(n). For each computable function g, let n(g) be the smallest n such that f(n) > g(n). Let n0 be the maximum of n(g) over all computable functions g, and assume this maximum is achieved for g0, that is, n(g0) = n0. De?ne a function g1 that is equal to g0 for all values except for n0, and for n0 we have g1(n0) = f(n0). This function g1 is computable because 1) g0 is computable and 2) g1 differs from g0 in only one point. By de?nition, n(g1) = n(g0) + 1, and this contradicts the fact that n(g) was maximized at g0.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.