u/42e1 · 12 pointsr/compsci

If you're interested in learning more about Turing's paper that introduced the Turing Machine, I highly recommend the book The Annotated Turing. It's by the same person who wrote Code, which is an oft-recommended book on this sub-reddit.

u/gunder_bc · 11 pointsr/learnprogramming

Learn some math, yes. Algebra, Discrete Math, Inductive Logic, Set Theory. Calc and Matrix Algebra are good for specific things, and just in general to beef up your math skills. But don't get hung up on it too much. It's a good thing to always have going in the background.

Start to think about how all computation is math - check out The Annotated Turing and really wrap your head around both what Petzold is talking about and what Turing is talking about.

That may require you to take a step back and study Formal Languages, Finite State Machines, and other related concepts (all the stuff that lets you build up to Regular Expressions, etc). Turnings thesis really gets to the heart of a computation, and those concepts build on that.

Then go learn LISP just to bend your brain some more.

Comp Sci is a fascinating subject, and you're off to a good start by thinking about what that Stack Overflow commenter meant - how are all languages similar? How do they differ? What's the underlying problem you're solving, and what are different ways of solving it? How do the tools you choose alter your solution?

Try writing something relatively simple (say, a program that plays Checkers or Tic-Tac-Toe and always wins) in a few different languages (start with ones you know, then learn some new ones to see how - if you've worked with Procedural or OO languages, try Functional ones).

u/fj333 · 11 pointsr/compsci

Have you seen the book The Annotated Turing?
https://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055

u/maybefbi · 10 pointsr/compsci

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

u/rheimbuch · 6 pointsr/programming

Alan Turing's original paper that introduced the Turing Machine is a great read. The Annotated Turing is a great way to both read and understand the paper if you don't have a background in compsci. It doesn't assume much more than highschool math, and the whole of Turing's paper is inline with the explanations.

u/Rikkety · 6 pointsr/AskComputerScience

Check out The Annotated Turing by Charles Petzold. It's Turing's paper on the Entscheidungsproblem which introduces Turing Machines, annotated with a lot of background information and some stuff about Turing's career. Very interesting stuff.

I can also recommend Code, by the same author which describes how a computer works from basic principles. It's doesn't have a lot of material on Turing, but it's certainly an interesting read for anyone interested in Comp Sci.

u/amair · 5 pointsr/math

Some good readings from the University of Cambridge Mathematical reading list and p11 from the Studying Mathematics at Oxford Booklet both aimed at undergraduate admissions.

I'd add:

Prime obsession by Derbyshire. (Excellent)

The unfinished game by Devlin.

Letters to a young mathematician by Stewart.

The code book by Singh

Imagining numbers by Mazur (so, so)

and a little off topic:

The annotated turing by Petzold (not so light reading, but excellent)

Complexity by Waldrop

u/KatsuCurryCutlet · 4 pointsr/learnmath

Hmm alright, considering your background, I'd probably recommend you giving Michael Sipser's Introduction to Theory of Computation a read (I sure there are many electronic copies floating around on the Internet). I think they cover the prerequisite math concepts required in a preliminary chapter before the content which I highly recommend you spend some time on. It works it's way up by walking you through notions of computations in increments, first through finite state automata before adding in more features, working its way up to a Turing machine. You can skip most of the exercises, since those are mostly for graduate students who need practice before undertaking research. If you ever get confused about concepts along the way just drop me a PM or a question in /r/askcomputerscience and I'm sure the community would be happy to help out.

Also if you're interested I could mail you my copy of (meaning a copy that I had bought some time ago, not that I wrote it) the Annotated Turing. It does a great job of explaining the concept of a Turing machine provided a non-mathematical and non-CS background. I'd be more than happy to share my books with people who are interested, plus there's no use in me keeping it around now that I'm done with it.

Just bear in mind that unlike most of science, the concepts here are very abstract, there aren't many direct physical implications, this really is a pure study of notions at play. i.e. how does one go about studying "how to do things" and its implications. A lot of details such as "how can such a machine exist with an infinite tape? what moves it? how does it implement its decision making scheme?" are all unimportant and ultimately inconsequential to the study itself.

Instead, what we care about are things like "I have a problem, is it possible for me to come up with a solution (algorithm) for it? Or is it logically impossible?" or things like "I have come up with a way to make a "computer", can it do things that other computers can? If I had to make it sort an arbitrary set of numbers so that they are ordered numerically, can my computer do it?". Turing machines, are a tool to help us reason about formally around these sort of arguments, and to give insight into what we can qualify as "computation". Further down the line we even ask questions like "are some problems inherently more 'difficult' than others?" and "if I can solve problem B, and I somehow use the solution for problem B to solve some other problem A?"

Perhaps this all sounds perplexing now, but maybe just go through some content and spend time reading a little and these should start to make a little more sense. good luck with your future endeavors on this journey!

u/kadhai · 4 pointsr/compscipapers

Charles Petzold's annotated version of this paper http://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055/ref=sr_1_1?ie=UTF8&amp;s=books&amp;qid=1280607006&amp;sr=8-1 is definitely worth reading, in my opinion.

u/lkh01 · 3 pointsr/compsci

I read The Annotated Turing by Charles Petzold while I was in high school and it really sparked my love for logic, math and computer science. So, as far as popular science books go, I can't not recommend it.

Right now I'm interested in programming languages, and I think TAPL is a great resource. The (relatively) new blog PL Perspectives is also pretty cool, and so is /r/ProgrammingLanguages.

u/lowlycollegestudent · 3 pointsr/compsci

I know that this is way more on the theory/mathematics side of the spectrum than CODE, but Charles Petzold also wrote a book called The Annotated Turing that I really enjoyed. He took Alan Turing's original paper on computability which was about 30 pages and annotated it until he had about a 400 page book. There were a couple of chapters in the middle that got a bit dense, but he did a fantastic job of making the subject more approachable and understandable.

u/onetwosex · 3 pointsr/greece

A book. I've got this suggestion from Uncle Bob.

https://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055

u/prince_muishkin · 3 pointsr/math

Turing's paper on computability I think is quite good, it's very well presented here. The course on computability I'm doing now hasn't added much, but discussed computability in more generality. I think it helped my understanding of computability is showing you can really do the nitty gritty details.

Can't remember where I found it but Godel's paper "On Formally Undecidable Propositions of Principia Mathematica and Related Systems" I found to be interesting in seeing the way my course in Logic could be down differently.

u/FBC · 2 pointsr/AskReddit

1984
Brave New World
E=mc^2
A Brief History of Time
The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

u/Wulibo · 2 pointsr/PhilosophyofScience

Examples of additional, unorthodox reasons to reject the basilisk on top of the obvious:

Someone actually doing something as stupid and evil as making the basilisk who is also capable of doing so is probably likely only on the same scale or less as the existence of God, even if you're a fairly strong Atheist. Anyone worried about being damned by a basilisk should feel safe knowing that with a relevant probability, God will save you from that damnation (I've argued at length here and elsewhere that infinite utility/disutility breaks decision theory since infinity*0.000001=infinity, so even if you're really worried that you're the simulation, your expected amount of pain moving forward isn't very high).
Go read Turing's On Computable Numbers. There's a proof that goes something like that some proposition x about computers can't be argued/proven/believed by computers due to the nature of x and the nature of computers. In proving this, it becomes very obvious that x. Therefore, with mathematical certainty, the human mind as is cannot be simulated on any sort of computer, so you're not a simulation. I've simplified to the point of essentially being incorrect, so if you want the full proof, find yourself a copy of The Annotated Turing and come talk to me after you read it for the relevant detailed argumentation after. In short I'd consider it a theorem of set theory that humans are incomputable.
The basilisk can be modeled as a Pascal Mugger. First, to explain, the Pascal Mugger is a critique of Pascal's Wager whereby you imagine encountering an unarmed mugger, who threatens to cause some sort of disaster unless you hand your wallet over; no matter your priors, there exists some disaster serious enough that you should be willing to hand over your wallet no matter how unlikely you find the mugger's capacity to cause it. Most interestingly, if you simply walk away from the mugger, the mugger doesn't even have reason to carry out its threat if possible; it would have no way of convincing you beforehand, and has nothing to gain. Likewise, the basilisk has no reason to torture anyone who would never have helped it, ie someone who is committed to a decision theory where the basilisk's threat is empty. So, if you ever fail to get pascal mugged (and btw, pretty much everyone agrees that you should just walk away from the mugger), this should count for the basilisk simulating you (again, impossible) as a sufficient test result to decide not to torture you. In the interest of expediency, I'll let you know right here for unrelated reasons that I have the capacity to immediately cause all souls that have ever lived to wink out of existence. If you don't PM me within 5 minutes of reading this, and I'll know, with your bank details so that I can take all your money at my leisure, I will do so. I will also post that you did so directly to /r/philosophyofscience so others who feel like it can pascal mug you. If you're confused as to why I'd say something like this, reread this bullet point... ideally for more than 5 minutes.

The fact that I need to go to such inane, ridiculous lengths to get past what I consider the "obvious" reasons to reject the basilisk should tell you how little you need to worry about this. It is only at this level of complexity that these objections to the basilisk stop being the obviously good-enough ones.

u/coforce · 2 pointsr/RedditDayOf

His original paper can be found here. If you find it a bit dense then you may be interested in reading an annotated version of his work found from this wonderful book.

u/cryptocached · 2 pointsr/bsv

The Annotated Turing is a fairly approachable book. It contains the entirety of Turing's paper while providing contextually-relevant historical and mathematical background.

u/rowboat__cop · 2 pointsr/programming

If you liked “Code” I suggest you read his
“Annotated Turing” next --
fascinating paper, fascinating book.

u/herrvogel- · 2 pointsr/ColorizedHistory

If anyone is really interested in is his life and what he accomplished, I can recommend this book. It is basically his paper on turning machines, but step by step explained + some details on him as a person.

u/nath_schwarz · 1 pointr/cspaperbot

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

u/finarne · 1 pointr/explainlikeimfive

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_

u/Sid99999 · 1 pointr/math

forgot to mention this https://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055

u/CSMastermind · 1 pointr/learnprogramming

Entrepreneur Reading List

u/PhyxsiusPrime · 1 pointr/furry

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.

u/StringyLow · 1 pointr/learnprogramming

Here's what you're looking for:

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

u/kunjaan · 1 pointr/compsci

There are books that are compendium of computing such as

http://www.cs.brown.edu/people/jes/book/
Guide to Turing's Papers

but they still require some effort on your side.

It would be better if you rephrase the question from "Cliff Notes" to "beginners intro that is not Sipser" : )

u/rdar1999 · 1 pointr/btc

https://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055

http://gen.lib.rus.ec/search.php?req=the+annotated+turing&amp;open=0&amp;res=25&amp;view=simple&amp;phrase=0&amp;column=def

A better source to learn what Turing's paper was all about with explanations of the concepts.

Reddit reviews The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

27 Reddit comments about The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine:

Entrepreneur Reading List

Computer Science Grad School Reading List

Video Game Development Reading List