| Halt is a decision problem, TFNP is a combinatorial problem constructed of decision problems. The HALT decider is a total Turing machine that represents a total function. I am struggling to explain this in a rigorous fashion, and there are many open problems. NP is where the answer "yes" is verifiable in polynomial time. co-NP is where the answer "no" is verifiable in polynomial time. NP is equivalent to second order predicts logic where the second term is existential 'there exists..' co-NP is equivalent to second order predicts logic where the second term is universal 'for any' We know P=co-P, or that the yes and no answers are both truthy. We think that NP!=co-NP Many useful problems are semi-decidable or recursively enumerable. Determining if a computable function is total is not semi-decidable. It is the subtle difference between proving a TM halts for any input vs halts for each input. Termination analysis is the field of trying to figure out if it halts for each input. It is actually harder than HALT, being on the second level of PH on the co-NP side. If that granularity isn't important to you, I personally don't think there is much of a risk in using the decidable metric as a lens. Just remember that something is decidable if and only if both it and its complement are semi-decidable. Semi-decidable problems often have practical applications even without resorting to approximations etc ... |
You claimed in GGP that deciding whether a function is total is a TFNP problem. In particular, that would make it decidable. But the counter-claim is that deciding whether a function is total is actually an undecidable problem.
I've also examined a definition of TFNP and I don't see how it is related to the problem of deciding if a function is total. Rather, the definition seems to require that the function in question be total.