Talk:One man's lecture notes on computability theory

Generally, an introductory course on computability would first go though the Chomsky hierarchy starting with regular languages and DFAs, so it might be a good idea to link the Wikipedia article wikipedia:Chomsky hierarchy AP295 (discuss • contribs) 03:36, 12 November 2023 (UTC)

I should also mention that Godel's incompleteness theorem isn't exactly about computability, but whether or not certain proofs exist within a given formal logic theory. It essentially states that in any "sufficiently powerful" (the exact conditions are probably on the wikipedia page) theory, there are true sentences for which there exists no proof within that theory. You'd probably only run into this result in a course on mathematical logic, and you'd not be able construct a proof without being very familiar with FOL. AP295 (discuss • contribs) 00:30, 14 November 2023 (UTC)

Also, Wikipedia has a list of undecidable problems somewhere, so that would be a good link to include. AP295 (discuss • contribs) 00:33, 14 November 2023 (UTC)

Thanks. The scope is based on what Luboš Brim does, and that seems to rather closely follow the book Theory of Recursive Functions and Effective Computability, whose syllabus I now added to the article.

What Luboš Brim does concerns computability on positive integers with zero, defining a computable function as one that is from N_0 --> N_0, is possibly undefined for some inputs, and is computed by a computational mechanism. Thus, the domain is of numbers, not strings over alphabet. And the automata and formal language theory deals with sets of strings over alphabet (not necessarily an alphabet but any finite set of elements sequences of which one may want to consider). While integers can be interpreted as strings (they can be first interpreted as bit sequences, and then as anything one knows from computing using a programmer's intuition), this is not necessarily the default or most natural interpretation. And thus, the context-free grammar/pushdown automaton (PDA) as computational mechanisms do not directly make sense on sets of integers (am I wrong?)

The alphabet of a DFA or PDA or Turing machine is arbitrary. AP295 (discuss • contribs) 07:26, 14 November 2023 (UTC)

Indeed, Gödel's incompleteness theorems are not in the book syllabus. The connection that I see is that the incompleteness theorems apply not only to Peano arithmetic but also to its extensions. One has to ask: what kinds of (infinite) supersets of Peano axioms do we have in mind as candidate sets of axioms aiming at completeness? And the answer is, from what I remember, only such sets as are programmatically enumerable/outputable, also called "recursively enumerable". Indeed, Peano axioms themselves are infinitely many and are finitely represented via axiom schema(ta). If we lift the programmatically-enumerable requirement, we can take the model of Peano arithmetic that we consider to be the standard positive integers with zero, consider sentences (closed formulas) true in that model, and throw all the true sentences in as axioms, thereby obtaining completeness for free.

In the usual context, completeness or incompleteness is a property of a formal theory itself, not to any set of sentences within the theory. You can't add more axioms (at least not any recursive set of axioms) to peano arithmetic to make it "complete" (though I think there are less powerful formal theories for which incompleteness holds), even though you can technically refer to the set of all true sentences within peano arithmetic. Edit: You're right, the incompleteness theorem does require a recursive set of axioms, so if you drop that requirement then I suppose you could technically add the set of all true sentences, but then such a theory is not very useful. You are essentially correct about that part, but there's no recursive set of axioms that you can add so that every true sentence is provable in that theory. AP295 (discuss

You're right. I read "what kinds of (infinite) supersets of Peano axioms do we have in mind as candidate sets of axioms aiming at completeness? And the answer is, from what I remember, only such sets as are programmatically enumerable/outputable, also called "recursively enumerable"." and thought you might be trying to find such an infinite-but-recursive completion. (I have trouble with word/sentence orderings sometimes, as evidenced by the copious editing I do to most of my posts/replies.) Generally though, undecidability is much more easily demonstrated using a turing machine with the halting problem, the incompleteness theorem requires much more 'build-up'. That was pretty much my point. AP295 (discuss • contribs) 15:54, 14 November 2023 (UTC)

Link to list of problems included; thanks.

--Dan Polansky (discuss • contribs) 07:14, 14 November 2023 (UTC)