Give a direct proof that the set {x|Phi_(x)(1)darr} (which is a set of program numbers that halt on input 1) is not recursive.

assuolareuz

assuolareuz

Open question

2022-08-14

Give a direct proof that the set { x | Φ x ( 1 ) } (which is a set of program numbers that halt on input 1) is not recursive.

Answer & Explanation

Jamir Young

Jamir Young

Beginner2022-08-15Added 11 answers

Halting problem: given M, Turing machine and input x,decide if M ( x ) halts .so you want to find a computable functions that take instance of Halting problem and convert it to instance of this problem .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school geometry

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?