pith. sign in

arxiv: 1410.7103 · v2 · pith:4JASXLNNnew · submitted 2014-10-27 · 💻 cs.LO · cs.PL

Confusion in the Church-Turing Thesis

classification 💻 cs.LO cs.PL
keywords modelchurch-turingcomputabilitycomputationsequalityequivalentprogrammingthesis
0
0 comments X
read the original 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 lambda-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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.