๐ฎ
๐ฎ
The Ethereal
Unconstrained Church-Turing thesis cannot possibly be true
January 15, 2019 ยท The Ethereal ยท ๐ Bull. EATCS
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Yuri Gurevich
arXiv ID
1901.04911
Category
cs.LO: Logic in CS
Cross-listed
cs.CL,
cs.DS,
math.LO,
quant-ph
Citations
4
Venue
Bull. EATCS
Last Checked
5 months ago
Abstract
The Church-Turing thesis asserts that if a partial strings-to-strings function is effectively computable then it is computable by a Turing machine. In the 1930s, when Church and Turing worked on their versions of the thesis, there was a robust notion of algorithm. These traditional algorithms are known also as classical or sequential. In the original thesis, effectively computable meant computable by an effective classical algorithm. Based on an earlier axiomatization of classical algorithms, the original thesis was proven in 2008. Since the 1930s, the notion of algorithm has changed dramatically. New species of algorithms have been and are being introduced. We argue that the generalization of the original thesis, where effectively computable means computable by an effective algorithm of any species, cannot possibly be true.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Logic in CS
๐ฎ
๐ฎ
The Ethereal
Safe Reinforcement Learning via Shielding
๐ฎ
๐ฎ
The Ethereal
Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks
๐ฎ
๐ฎ
The Ethereal
Heterogeneous substitution systems revisited
๐ฎ
๐ฎ
The Ethereal
Omega-Regular Objectives in Model-Free Reinforcement Learning
๐ฎ
๐ฎ
The Ethereal