>(And I think I read somewhere that Turing's introduction of those concepts in the first place was heavily influenced by Godel's work. So if that's true then in that sense historically Godel's work is behind a lot of our understanding of computation.)
I read that Turing invented the machine to solve the same problem Gödel was working on. According to the book the Annotated Turing (a book-length explanation of Turing's first paper on the Turing machine), Turing was also trying to formalize the proof process and use it to prove that some proofs are impossible within a given formal system. He apparently considered not publishing his paper after being "scooped" by Gödel's much more succinct proof.
Not a whole lot actually. There is a really great book which walks through the whole paper step by step and explains each part, as well as giving quite a bit of the necessary background.
http://www.amazon.com/The-Annotated-Turing-Historic-Computability/dp/0470229055
Item | Current | Lowest | Reviews |
---|---|---|---|
The Annotated Turing: A Guided Tour Through Alan… | - | - | 4.6/5.0 |
^Item Info | Bot Info | Trigger
Books. Textbooks, pop-math books, and all the books in between. If you have a particular topic that you're interested in, get some books on it.
r/math pretty regularly has threads of book recommendations. The American institute of Mathematics has a list of open textbooks on a bunch of topics if you don't want to break the bank on proprietary textbooks. If you want something a bit more fun and loose than a textbook, Raymond Smullyan wrote a bunch of books that use logic puzzles to explain various topics (mostly Gödel and formal logic, now that I'm looking at the list). I particularly enjoy books that mix in the history of a topic with the math itself; for example I've been reading The Annotated Turing by Charles Petzold, which covers both the history of the work leading up to Turing's 1936 paper (e.g. Hilbert, Cantor, Diophantus), as well as walking through the paper itself.
There's a bunch of math stuff online (youtubers, Medium.com blogs, and the like), and these can be great for discovering a topic, but I find that books are still the best way to really learn a topic.
No, but I’m currently reading this and it’s fantastic
If you want a detailed breakdown of Turing’s seminal paper Charles Petzold’s book is great:
https://www.amazon.co.uk/Annotated-Turing-Through-Historic-Computability/dp/0470229055/ref=nodl_
In that vein, you might like Annotated Turing, if you have any interest in Computer Science. It's an annotated version of Turing's most famous paper (the one that basically establishes the basis for computers and computer science), but it can be a little dry if you're not inherently interested in the topic.
Also, the much more fun Logicomix (yes, a math comic book :D), about Bertrand Russel's quest to establish a logical basis for all of mathematics.
Title: On Computable Numbers, with an Application to the Entscheidungsproblem
Authors: Alan Turing
Link: http://plms.oxfordjournals.org/content/s2-42/1/230.full.pdf
Abstract: In just 36 pages, Turing formulates (but does not name) the Turing Machine, recasts Gödel's famous First Incompleteness Theorem in terms of computation, describes the concept of universality, and in the appendix shows that computability by Turing machines is equivalent to computability by λ-definable functions (as studied by Church and Kleene). Source
Comments: In an extraordinary and ultimately tragic life that unfolded like a novel, Turing helped break the German Enigma code to turn the tide of World War II, later speculated on artificial intelligence, fell victim to the homophobic witchhunts of the early 1950s, and committed suicide at the age of 41. Yet Turing is most famous for an eerily prescient 1936 paper in which he invented an imaginary computing machine, explored its capabilities and intrinsic limitations, and established the foundations of modern-day programming and computability. From his use of binary numbers to his exploration of concepts that today's programmers will recognize as RISC processing, subroutines, algorithms, and others, Turing foresaw the future and helped to mold it. In our post-Turing world, everything is a Turing Machine — from the most sophisticated computers we can build, to the hardly algorithmic processes of the human mind, to the information-laden universe in which we live. Source