PAI Private Arithmetics Institute       

Natural Numbers, Recursion, Geometry, Symmetry, Axioms, Logic, Metalanguage and more 


The Snark, a counterexample for Church's thesis ?


In 1936 Alonzo Church put forward his thesis that recursive functions comprise all effectively calculable functions. Whereas recursive functions are precisely defined, effectively calculable functions cannot be defined with a rigor that is requested by mathematicians. There has been a considerable  amount of talking about the plausibility of Church's thesis, however, this is not relevant for a strict mathematical analysis. The only way to end the discussion is obtained by a counterexample.

The author has developed an approach to logics that comprises, but also goes beyond predicate logic. The FUME method contains two tiers of precise languages: object-language Funcish and metalanguage Mencish. It allows for a very wide application in mathematics from recursion theory and axiomatic set theory with first-order logic, to higher-order logic theory of real numbers etc. .

The concrete calcule LAMBDA of natural number arithmetic with first-order logic has been defined by the author. It includes straight recursion and composition of functions, it contains a wide range of so-called compinitive functions, with processive functions far beyond primitive recursive functions. All recursive functions can be represented in LAMBDA too. The unary Snark-function is defined by a diagonalization procedure such that it can be calculated in a finite number of steps. However, this effectively calculable function transcends the compinitive functions and presumably the recursive functions. The defenders of Church's thesis are challenged to show that the Snark-function is recursive. Another challenge asks for an example of a recursive function that cannot be expressed as a compinitive function, i.e.  without minimization.

They sought it with thimbles, they sought it with care;

They pursued it with forks and hope;

They threatened its life with a railway-share;

They charmed it with smiles and soap      The Hunting of the Snark (An Agony in Eight Fits), Lewis Carroll 1876