computability   292

« 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
7 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

« earlier    

related tags

4141  ::wikipedia::  academia  agda  ai  algorithms  an-example-would-be-good-about-now  analysis  articles  arxiv  automata  bbc  biology  brian-greene  caltech  categorytheory  cellular-automata  chess  church-turing  church  classics  complexity-theory  complexity  complexity_theory  compsci  computation  computational-complexity  compute  computer-science  computermaths  computing  consciousness  correctness  cryptography  cs  decidability  definition  demoscene  digital-philosophy  digital-physics  discussions  domains  edward-fredkin  equilibrium  evolution  fluid_mechanics  formal-languages  formal_mathematics  foundational-work  function  functional  game-of-life  game_theory  games  godel  goedel  hacker-news  halting  haltingproblem  have-watched  history-of-science  history  incompleteness  independence  information  information_theory  juergen-schmidhuber  kolmogorov-complexity  lambda-calculus  lambda  language  learnability  logic  losangeles  lss  machine  machinelearning  math  mathematics  maths  measurement  medium  misunderstanding  models  monad  nash  normalization  notes  np-complete  np  nudge-targets  number-theory  numbers  p/np  paper  papers  pdf  philosophy  physics  pnp  prediction  problem  productivity  program  programming  proofs  pullum  quantum-mechanics  quantum  quantum_information  quantum_mechanics  rather-interesting  real  reality  recursive  reference  representation  representations  req  resource  reversemathematics  rewriting-systems  russell's-paradox  rust  science  self-interpreter  settheory  seuss  slides  smallcode  software  structure  tcs  tedslaman  term  termination  theoretical-computer-science  theory  to-cite  to-understand  to-write-about  topology  totality  turing-machines  turing  type  typetheory  ucla  videos  wikipage  wikipedia  word-cloud  word  λcalculus 

Copy this bookmark: