Cornerstones of UndecidabilityThis book presents one of the most intellectually challenging aspects of computer related mathematics/logic in a way which should make it accessible to a wider audience. The authors look at different types of reduction to show undecidability, but do so using the novel approach of conversation between three famous mathematicians - sometimes using their own words and sometimes in an adapted form. The authors are of international repute and they provide a modern and authoritative treatment of undecidability with special emphasis on rigorous proofs. Numerous worked examples are included. |
Common terms and phrases
A₁ alphabet arbitrary argument Assume axioms b₁ binary bits Bolgani borderline boxes C₁ Church's Thesis command complexity computation Consequently consider consists construct context-free defined definition denote digits Diophantine Diophantine set DOL systems effective procedure empty encoding equation equivalence problem Example finite formal system formula g and h G₁ given Gödel halting problem Hence Hilbert's Tenth Problem holds infinite input instance PCP intuitive Kolmogorov complexity Lemma length letters linear grammars mathematics matrix morphisms nonnegative integers nonterminals notation notion obtain pairs partial recursive function polynomial Post Correspondence Problem prefix prefix-free productions proof of Theorem provable R₁ random recursively enumerable languages recursively enumerable sets register machine regular language representation resp S₁ satisfied semigroups sequence sim(C solution specific Step Subgoal Tarzan theory truth-value Turing machine TM u₁ undecidable values variables w₁ w₂ Z-rational