Computability


Introduction - What Church's thesis is and what it is not (relative to the principles of informal computability theory, especially those of Ebbinghaus)


4.1 Four related theses
Prologue and Preliminaries: Doublets, Dominoes, reductions, metamathematics as empirical theory and naturalism
4.1.1 Post's thesis (Did Post anticipate Church's thesis?)
4.1.2 Turing's definition/thesis
4.1.3 Gödel's thesis (Did Gödel anticipate Church's thesis?)
4.1.4 Gandy's thesis
Epilogue: Church's thesis and Artificial Intelligence



4.2 Church's definition /thesis and its epistemological status
4.2.1 Church's original formulation
4.2.2 The so-called evidence
4.2.2.1     Arguments for the thesis
4.2.2.2     The standard argument for the converse
4.2.2.3     The argument from Martin-Löf randomness
4.2.3 Definition, thesis, hypothesis, or…?
4.2.3.1     The early debate
4.2.3.2     Further comments on the epistemological status
4.2.3.3     Mathematical theses
4.2.3.4     Comparisons and analogies
4.2.3.5     Is the thesis unprovable? Is it refutable
4.2.3.6     A brief resumé


4.3         Arguments against the converse of Church's thesis
4.3.1 Algorithmicity versus constructivity
4.3.1.1     Péter's vicious circle argument and Heyting's counter-examples
4.3.1.2     Excentric counter-examples
4.3.1.3     Extensional recursiveness versus intensional computability
4.3.2 Algorithmicity versus primitive recursiveness
4.3.3 Algorithmicity versus feasibility
4.3.4 The argument from unknown computational complexity



4.4         Arguments against Church's thesis
Preliminaries: Relative computability, computability versus chance
4.4.1 Kalmár's so-called implausibility argument
4.4.2 Bowie's argument from random number generators
4.4.3 Thomas' argument
4.4.4 Bringsjord's "narrational case"
4.4.5 The argument from machine

Epilogue: Conway's Life