# confusion in the church-turing thesis

# abstract

The Church-Turing Thesis confuses numerical computations with symbolic computations. In particular, any model of computability in which equality is not definable, such as the λ-models underpinning higher-order programming languages, is not equivalent to the Turing model. However, a modern combinatory calculus, the SF-calculus, can define equality of its closed normal forms, and so yields a model of computability that is equivalent to the Turing model. This has profound implications for programming language design - https://arxiv.org/pdf/1410.7103v2.pdf

# SF-calculus

# concepts

- numerical computations
- symbolic computations
- turing model
- equality
- computability
- equivalence
- [not] definable
- limits of expressive power
- true origins of the church-turing thesis, first publication, when and where
- numerical functions
- symbolic functions
- soundness of arguments / faulty argument
- numerical problems
- computable solution
- positive integers
- recursion / recursive
- effective calculability
- effectively calculable
- Gödel numbering / representation

# people

- church
- stephen cole kleene
- soare

# books

- introduction to metamathmatics