Computability & Unsolvability, 第 10 巻

A-recursively A-semicomputable algorithm arithmetical logic called Chap combinatorial system completely computable functional completely recursive constructive Corollary decision problem defined DEFINITION 5.1 diophantine predicate domain exists finite function first-order logic follows at once functional F given Gödel number Hence hq'h Immediate from Theorems instantaneous description integers internal configuration Kleene hierarchy LEMMA mathematical modus ponens n-ary n-tuples normal system numerical predicate obtained ordinal Ɔ A Ɔ p₁ partial propositional calculus partial recursive function partially computable PgiQ predicate symbol primitive recursive function problem is recursively proved qi Sj quadruples r₁ recursively enumerable set recursively solvable result rules of inference S₁ semi-Thue system semicomputable predicate semigroup sequence simple Turing machine suppose symbol of degree Theorem 3.1 Thue system Tm(Z total functions U(min universal quantification unsolvable decision problem w-consistent word write