Constructive version of decidability?

Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). A problem statement that is easier to explain ("is P = NP?") is also decidable: either yes or no, and so one of the two TMs that always output those answers decides the problem. Formally, we can decide the set $S :=\{|\{P, NP\}|\}$: either the machine that outputs $1$ only for input $1$ and otherwise $0$ decides it, or the machine that does so for input $2$.

One of them boiled it down to basically this objection: if that's how weak the criterion of decidability is - which implies that every question which we can formalize as a language that we can show to be finite is decidable - then we should formalize a criterion that doesn't render any problem with finitely many possible answers that's formalizable in this way decidable. While the following is possibly a stronger criterion, I suggested that maybe this could be made precise by requiring that decidability should depend on being able to show a TM, basically proposing an intuitionist view of the matter (which I don't incline towards - nor do any of my colleagues, all of them accept the law of excluded middle).

Have people formalized and possibly studied a constructive theory of decidability?

G. Bach

Posted 2016-03-22T12:21:43.207

Reputation: 1 978

My suspicion is that constructive computability would be quite boring. (I find their objection weaker than the definition they complain about.) – Raphael – 2016-03-22T15:18:03.443

2How about a machine that searches in parallel for proofs of $\mathsf{P} = \mathsf{NP}$ and of $\mathsf{P} \neq \mathsf{NP}$ and acts accordingly? Assuming that the question is decidable, the machine will always halt and accepts the language. Do you allow that? – Yuval Filmus – 2016-03-22T15:49:52.537

@YuvalFilmus Hm, it's circular to show I can decide a problem under the assumption that I can decide it - maybe I misunderstood you? – G. Bach – 2016-03-22T16:08:17.257

@G.Bach The difference is that my machine is explicit, only the proof that it halts is non-constructive. – Yuval Filmus – 2016-03-22T16:55:21.950

@YuvalFilmus The problem I'm having is that I don't see that a proof for either P = NP or P $\neq$ NP must exist; if I knew that, then what you suggest would work assuming we can enumerate proofs (e.g. via some form of Gödelization). Could you elaborate a bit? – G. Bach – 2016-03-22T19:53:30.620

1@G.Bach You don't see it because we don't know that it exists. But if you assume that $\mathsf{P} = \mathsf{NP}$ is not independent, then the program works. If it is independent, then your language itself is model-dependent, which is somewhat strange. – Yuval Filmus – 2016-03-22T22:33:37.070

there seem to be closely related questions of P vs NP that are not obviously decidable such as (say P≠NP) "what is the smallest $c$ such that SAT is solvable in $O(n^c)$ time." scott aaronson has a survey on P vs NP decidable question. but the short story is that there does not seem to be any compelling reason to expect undecidability problems with complexity theoretic questions, "yet". the Blum axioms (speedup/ gap etc) are worth some study as a case where there are some paradoxical results. also oracle results such as Baker Gill Solovay 1975 might be relevant. – vzn – 2016-03-23T02:06:58.150

@vzn That survey by Aaronson, do you mean "Is P v NP formally independent?"? Having read the first page of it, that seems like a worthwhile read. If you'd like credit for it, please post it as an answer. – G. Bach – 2016-03-23T09:04:49.023

@YuvalFilmus I thought about it some more, and the connection between decidability and independence is more relevant here than I would've thought. If you'd like credit for it, please post an answer - and if you have any additional remarks, that's even better. – G. Bach – 2016-03-25T21:40:02.953

Answers

I think the question you are trying to ask is "is computability theory constructive?". And this is an interesting question, as you may see by this discussion on the Foundations of Mathematics mailing list.

Unsurprisingly, it has been considered, since a lot of recursion theory was developed by people with constructive sensibilities and vice versa. See e.g. Besson's book and the venerable Introduction to Metamathematics. It's pretty clear that the first couple of chapters of recursion theory survive moving to a constructive setting with minimal changes: e.g. the s-n-m theorem, Rice's theorem or the Kleene recursion theorems survive unchanged.

After the first chapters though, things get a bit tougher. In particular, the higher levels of the arithmetic hierarchy are usually defined by a notion of truth. In particular, widely used theorems such as the Low Basis Theorem seem to be explicitly non-constructive.

Perhaps a more pragmatic response, though, is that these "paradoxically computable languages" are simply an idiosyncrasy, that can (and have!) been studied at great length, like non-measurable sets of reals, but that once the initial surprise has been overcome, one can move on to more interesting things.

cody

Posted 2016-03-22T12:21:43.207

Reputation: 7 463

Those look like great pointers, thanks! I'll leave the question open for another day or three, just to see whether someone knows other leads worth investigating. – G. Bach – 2016-03-23T08:55:08.690

I would also add Computability: A Mathematical Sketchbook by Douglas S. Bridges. He discusses the issue of classical reasoning vs. constructive reasoning in the introduction.

– Kaveh – 2016-04-11T23:19:06.340

In classical logic, every statement is either true or false in any given model. For example, any first-order statement about natural numbers is either true or false in the "real world" (known in this context as true arithmetic). What about Gödel's incompleteness theorem, then? It just states that no recursively enumerable axiomatization of true arithmetic is complete.

Regarding $\mathsf{P}$ vs. $\mathsf{NP}$, most researchers believe that $\mathsf{P} \neq \mathsf{NP}$, some that $\mathsf{P} = \mathsf{NP}$, and a handful entertain the belief that it is independent of (say) ZFC. Suppose that you're willing to admit that it's in fact not independent of ZFC (in the same way that you're willing to admit that ZFC is consistent in the first place). In that case, there is a completely explicit Turing machine that computes your language. The machine searches for proof of either $\mathsf{P} = \mathsf{NP}$ or $\mathsf{P} \neq \mathsf{NP}$ until one is found, and then proceeds accordingly. We can prove that this machine accepts your language, even though we still don't know what that language is exactly!

If you're not willing to admit that $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$ is decided by ZFC, then you can still ask whether there is an explicit Turing machine that accepts your language. I leave this mind-boggling question to the interested reader.

Yuval Filmus

Posted 2016-03-22T12:21:43.207

Reputation: 245 786

(disclaimer, a fuzzy answer to a fuzzy question which maybe fits better on cstheory). constructibility is a "big deal" in theoretical math but it shows up especially in continuous contexts such as the semifamous Banach-Tarski paradox. these paradoxes generally do not seem to have shown up in "more discrete" CS "so far". so what is (the analog/ parallel of) constructibility in CS? the answer seems not so clear. its a concept originating in math research more than CS and the two dont seem to be tied together on this particular crux too much "so far".

one answer is that theory of decidability actually seems to be a variation on constructibility ie it is a strict method of determining which sets are computable which appears to be closely connected.

constructibility at heart deals with some issues of "independence from ZFC" and those areas are considered at length in this paper by Aaronson wrt P vs NP, Is P vs NP formally independent?.

its not really shown that "paradoxes" seem to point toward constructibility issues, but one might take that as a rough guide for a rough analogy as in Aaronsons paper where he considers eg oracle results which seem to have some "paradoxical" flavor in particular Baker Gill Solovay 1975 result that oracles exist both such that P^A = NP^A and P^B≠ NP^B. other paradoxical like thms are the Blum gap and speedup theorems.

also is it merely a coincidence that CS focuses on "time/ space" constructible functions in its fundamental time/ space hierarchy theorems? (which then exclude Blum-like paradoxes almost "by design"?)

another answer is that this is under active investigation/ research eg as in this finding. constructibility is known to be tied up with "large cardinals" in math: Winning strategies for infinite games: from large cardinals to computer science / Ressayre.

Using the large cardinal axiom of “sharps” Martin proved analytic determinacy: the existence of a winning strategy for one of the players in every infinite game of perfect information between two players, provided the winning set of one of the players happens to be an analytic one. I modify and complement his proof so as to obtain a new proof of the Rabin, Buechi-Landweber, Gurevich-Harrington theorem of finite state determinacy: existence of a winning strategy computed by a finite state machine, when the player's winning sets are themselves finite state accepted.

vzn

Posted 2016-03-22T12:21:43.207

Reputation: 10 652