about · lately · live · notes · talks · writing · contact · thanks · support ·


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

people

books