The halting problem

Martin Raza December 01, 2020 at 17:42 1925 views 4 comments

We know that given any Turing machine m and any input n, we can construct a finite set of sentences ? and a corresponding halting sentence H such that ? ? H iff TMm eventually halts on input n. Thus if there were an effective method for determining that ? ? H then we could solve the halting problem and thereby refute the Church-Turing Thesis.
However, given that there is an effective positive test for first-order entailment, why cant we solve the halting problem by considering the negation of the halting sentence, viz. ? ? ¬H?

Comments (4)

Deleted User December 01, 2020 at 19:08 #476028 0 likes

This user has been deleted and all their posts removed.

Martin Raza December 01, 2020 at 19:17 #476031 0 likes

Reply to tim wood

The question is why can/cant? Explain why or why not we can consider solving the halting problem by consider the negation of the halting sentence

ssu December 02, 2020 at 01:36 #476117 0 likes

Reply to Martin Raza And doesn't a negation of H leave it quite open?

Like I cannot give the correct answer, yet here's my answer A and it's not it so there you go.

Many times people get sidetracked by noticing that there is a correct answer.

jgill December 03, 2020 at 00:49 #476426 0 likes

There is no halting problem concerning this thread.