HackerPapers

arXiv:1410.7103cs.LO

Confusion in the Church-Turing Thesis

Barry Jay, Jose Vergara

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
Journal reference
DOI
Subjects
cs.LOLogic in Computer Science cs.PLProgramming Languages

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2018 to Dec 2018. Found in 2 HN submissions from Aug 2022 to Aug 2022. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Ask HN: What has Haskell ever done for us? 1 comment

    • On the topic of time/space leaks in functional programming. Folks are working on enabling intensionality which will have profound implications for programming language design. See https://m.youtube.com/watch?v=4i4SNvlWnmM and https://github.com/Barry-Jay/SF and…

      ghuntleyView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.