• Martin Raza
    4
    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?
  • Deleted User
    0
    This user has been deleted and all their posts removed.
  • Martin Raza
    4


    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
    9.4k
    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
    4k
    There is no halting problem concerning this thread.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment

Welcome to The Philosophy Forum!

Get involved in philosophical discussions about knowledge, truth, language, consciousness, science, politics, religion, logic and mathematics, art, history, and lots more. No ads, no clutter, and very little agreement — just fascinating conversations.

×
We use cookies and similar methods to recognize visitors and remember their preferences.