# Deciding whether a turning machine guaranteed to halt solves sat [closed]

Suppose I give as input a Turing machine M guaranteed to halt in time n^c on inputs of length n for a universal constant c. Is there a Turing machine that given any such M can decide whether M solves SAT?

Remarks: - could it be that there is an N depending on c and the description size of M such that if M doesn't solve SAT it answers wrong on an input of length at most N?

• This is not a research-level question so is off-topic, here. Since it's been answered, it should probably be migrated to Computer Science Stack Exchange. – David Richerby Jan 8 '14 at 21:32
• I don't mean to discourage you but I don't think my comment is at all unfair. Once the fine details are sorted out, it seems likely that Philip White's answer will be correct: if P=NP, the problem is certainly trivial; otherwise, undecidability should follow quickly from Rice's Theorem and, thus, require only an undergraduate level of knowledge. Two people disagreeing on whether the first answer is 100% correct does not make it a research question. – David Richerby Jan 8 '14 at 22:35
• Like I said the n^c was rather arbitrary and can be switch,e.g. to 2^n - in which case P!= NP doesn't make the language empty.. the point is more about whether the promise about halting makes it decidable. I think it's quite an interesting research direction: given a potential witness' that P=NP - an algorithm that supposedly solves SAT, can we check whether it is correct – relG Jan 8 '14 at 22:44
• The running time restriction doesn't seem to make any crucial difference. Given a TM $M$, let $M'$ be the machine that simulates $M$ for $n^c$ (or $2^n$ or whatever) steps and rejects if $M$ has not yet halted. Deciding whether $M$ solves SAT with the promise is the same as deciding whether $M'$ solves SAT without the promise. Whether $M'$ solves SAT is undecidable by Rice's theorem. – David Richerby Jan 8 '14 at 22:51
• If I understand correctly Rice's thm implies it is undecidable whether given a TM M , it solves SAT. You want to say it also undecidable whether given a TM M (that maybe doesn't always halt) it solves SAT with in n^c (or some other f(n) ) steps. I don't see why the first statement implies the second – relG Jan 8 '14 at 23:14