theorem A.30 Church, Turing

open in the book · appendices/A-long-proofs.tex:2578 · p. 2805

Rests on

depends_on theorem A.17 Representability ¶
- depends_on definition A.16 Representability ¶
  - depends_on definition 3.80 Formal system ¶
- depends_on definition 3.93 Computable function, decidable set ¶
  - depends_on definition 3.92 Turing machine ¶
- depends_on lemma A.20 $\Sigma_{1}$-completeness ¶
  - depends_on definition A.18 $\Delta_{0}$ and $\Sigma_{1}$ ¶
    - depends_on equation A.119 eq:app-inc-order ¶
  - depends_on lemma A.19 Numerals behave ¶
    - depends_on definition 3.83 Peano arithmetic ¶
      - depends_on axiom 3.33 Peano axioms ¶
      - depends_on axiom 3.34 Principle of induction ¶
      - depends_on definition 3.80 Formal system ¶ ↺
    - depends_on equation A.118 eq:app-inc-Q-successor ¶
    - depends_on equation A.119 eq:app-inc-order ¶ ↺
    - proves proof app:A-long-proofs@proof-13 ¶
  - depends_on proposition 3.22 Algebra of propositions ¶
    - depends_on definition 3.17 Logical equivalence ¶
      - depends_on definition 3.12 Biconditional ¶
      - depends_on definition 3.14 Tautology ¶
    - depends_on definition 3.6 Truth table ¶
    - proves proof ch:01-logic-sets@proof-4 ¶
  - proves proof app:A-long-proofs@proof-14 ¶
- depends_on theorem A.25 thm:app-inc-primrec ¶
  - depends_on definition A.16 Representability ¶ ↺
  - depends_on lemma A.23 Sequence lemma ¶
    - depends_on definition A.22 Gödel's $\beta$ ¶
    - depends_on lemma A.21 Chinese remainder theorem ¶
      - proves proof app:A-long-proofs@proof-15 ¶
    - proves proof app:A-long-proofs@proof-16 ¶
  - depends_on lemma A.24 lem:app-inc-beta-delta0 ¶
    - depends_on definition A.22 Gödel's $\beta$ ¶ ↺
    - depends_on definition A.18 $\Delta_{0}$ and $\Sigma_{1}$ ¶ ↺
    - depends_on lemma A.19 Numerals behave ¶ ↺
    - proves proof app:A-long-proofs@proof-17 ¶
  - depends_on lemma A.19 Numerals behave ¶ ↺
  - depends_on lemma A.20 $\Sigma_{1}$-completeness ¶ ↺
  - proves proof app:A-long-proofs@proof-18 ¶
- proves proof app:A-long-proofs@proof-19 ¶
depends_on theorem 3.84 Gödel's completeness theorem, 1930 ¶
- depends_on definition 3.82 Consistency, completeness, soundness ¶
  - depends_on definition 3.80 Formal system ¶ ↺
  - depends_on definition 3.7 Negation ¶
- depends_on definition 3.80 Formal system ¶ ↺
- proves proof ch:01-logic-sets@prooflink-2 ¶
depends_on theorem 3.96 Turing ¶
- depends_on definition 3.93 Computable function, decidable set ¶ ↺
- depends_on definition 3.92 Turing machine ¶ ↺
- proves proof ch:01-logic-sets@proof-23 ¶
proves proof app:A-long-proofs@proof-24 ¶

Supports

Nothing declares a dependency on this node yet.

Neighborhood

Every logical edge within two steps of this node.

declared and complete
partly declared
a check failed
not graded
declared in the source
inferred from structure

Edges

type	direction	node	provenance	where
`cites`	→	A Note on the Entscheidungsproblem	derived	appendices/A-long-proofs.tex:2580
`cites`	→	On Computable Numbers, with an Application to the Entscheidungsproblem	derived	appendices/A-long-proofs.tex:2580
`depends_on`	→	Representability	declared	appendices/A-long-proofs.tex:2581
`depends_on`	→	Gödel's completeness theorem, 1930	declared	appendices/A-long-proofs.tex:2581
`depends_on`	→	Turing	declared	appendices/A-long-proofs.tex:2581
`proves`	←	app:A-long-proofs@proof-24	declared	appendices/A-long-proofs.tex:2584