The halting problem
  • 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?
    Martin Raza Options
  • tim wood
    9.3k
    considering the negation of the halting sentence, viz. ∆ ⊨ ¬H? — Martin Raza
    Meaning that Δ does not halt? But is not that the same problem? If Δ is not halting, that is not proof as to whether it will or will not halt, yes?

    Which maybe proves I do not understand the question. Sometimes brevity and concision is self-defeating. Could you make the question a bit more transparent?
    tim wood Options
  • Martin Raza
    4
    ↪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
    Martin Raza Options
  • ssu
    8.6k
    ↪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.
    ssu Options
  • jgill
    3.8k
    There is no halting problem concerning this thread.
    jgill Options
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.

Sign In Create Account

Categories