3 ms·
> These are the central questions in the formal study of computation. The field dates back to 1936, when Alan Turing first imagined a fanciful device, now calle
by tromp 3y ago
> These are the central questions in the formal study of computation. The field dates back to 1936, when Alan Turing first imagined a fanciful device, now called a Turing machine, that could perform any computation by reading and writing symbols on an infinite tape.
It dates further back to the 1920s when Moses Schönfinkel came up with Combinatory Logic [1], and the early 1930s when Alonzo Church came up with the lambda calculus [2]. These models however make a less suitable base for computational complexity theory.
[1] https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel
[2] https://encyclopediaofmath.org/wiki/Lambda-calculus https://encyclopediaofmath.org/wiki/Lambda-calculus
- benreesman 3y agoParent has probably seen this (or everything in it), but for others who are interested in this stuff (including Schönfinkel’s work) I recommend https://youtu.be/h0OkptwfX4g https://youtu.be/h0OkptwfX4g.
- YeGoblynQueenne 3y agoArguably it goes further back to Pearce and Frege, Boole, Pascal, Leibniz and all the way to Aristotle, who was probably the first to seek a way to formalise structured thinking. Turing meant his computational apparatus as a formalisation of the way a human mathematician solves a problem by computation, i.e. by the manipulation of symbols according to a set of formal rules. In that, he followed in a long line of others who had thought about the same experience and how eminently mechanisable it is. Pascal was the first to actually do it, for arithmetic.