recentpopularlog in

computability

« earlier   
Wikipedia: Kappa calculus
In mathematical logic, category theory, and computer science, kappa calculus is a formal system for defining first-order functions.
mathematics  logic  computing  computability  term  definition  resource  wikipage  ::wikipedia::  from twitter_favs
8 weeks ago by aalvaradoh
[1901.04911] Unconstrained Church-Turing thesis cannot possibly be true
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.
computer-science  rewriting-systems  formal-languages  computability  algorithms  to-understand 
february 2019 by Vaguery
Alan Turing, On computable numbers | Joel David Hamkins
What I was extremely surprised to find, however, and what I want to tell you about today, is that despite the title of the article, Turing adopts an incorrect approach to the theory of computable numbers. His central definition is what is now usually regarded as a mistaken way to proceed with this concept.

Let me explain. Turing defines that a computable real number is one whose decimal (or binary) expansion can be enumerated by a finite procedure, by what we now call a Turing machine. You can see this in the very first sentence of his paper, and he elaborates on and confirms this definition in detail later on in the paper.
computability  mathematics  number-theory  algorithms  rather-interesting  history-of-science  representation  to-write-about  ReQ 
december 2018 by Vaguery

Copy this bookmark:





to read