Theory of Computation | Hacker News Reader

Theory of Computation

ocw.mit.edu

122 pointscharlysl30 comments

Recently:

https://news.ycombinator.com/item?id=28807222

I'm sure this course is great. Sipser is a terrific teacher and his textbook on the subject looks excellent. I used to be into the subject myself and still hang around Scott Aaronson's blog where CS nerds tend to congregate. But, I think there was an era when being a good programmer meant knowing a lot about algorithms, and the pinnacle of the programmer's art was supposed to be knowing how to write a compiler (look at the intended outline of Knuth's TAOCP as written in the 1960's: it was to be a 7 volume buildup finishing with stuff like parsers).

These days, I think CS algorithms are pretty well packaged in code you can download, they're not even that relevant to most problems most of us face in our work, and being really clueful instead involves more traditional math than CS per se. This might be something like a cycle returning to where it started. I find myself wishing I knew more about probability and statistics (useful all over the place), abstract algebra (fancy type systems use it), a reasonable amount of mathematical logic (program verification), number theory (cryptography), geometry and maybe even functional analysis and PDE's (machine learning), etc. I'm probably more into math than the average programming geek but I still feel like a helpless little kid when I try to understand these topics. This is me, wagging my tail in the picture (j/k):

https://www.starshipnivan.com/blog/wp-content/uploads/2009/0...

but in all sorts of areas of programming, it always seems like there is a "doorknob principle" just outside my reach. To the extent that I have any motivation to study math these days, I think the above subjects are more likely to be useful than CS theory per se. YMMV.

This is why learning to work with others, getting into the right teams etc matters. We all have 6 inch chimp brains. The universe will not fit into it no matter what you do individually.

Groups of chimps > Single chimp roaming the jungle in the darkness.

The math I mentioned is all pretty accessible to the average math grad student who wants to study it. An actual research mathematician would have a good grounding in all of it except for maybe logic. That is unfortunate since logic is important and every technical person should probably study some (i.e. the equivalent of an undergrad class where you study things like the Gödel incompleteness theorem).

If I look at mathoverflow with my 6 inch brain, it somehow seems like everyone over there managed to get a 12 inch brain or larger, except under the lo.logic tag. There, tons of the questions are at the basic undergraduate level, which is good for me because I can sometimes understand them, but they are nowhere near the research level expected on the rest of that site.

I do like your formulation about the 6 inch chimp brain.

Math overflow is NOT a learning environment.

Its more a Library than a School. There are many difference between those two spaces.

Think about why no one, anywhere in the world, across all cultures, drops their kids of at a library instead of a school...

I agree about mathoverflow not being a learning space per se, but I've learned a lot there, and I also learned a lot in libraries (probably more than I did in school).

> An actual research mathematician would have a good grounding in all of it except for maybe logic. That is unfortunate since logic is important

Really? I took two courses in discrete math and both started with logic. How can you move on to proofs without logic? I can't imagine a "research mathematician" without a sound basis in it.

I mean mathematical logic, where you study proofs as mathematical objects, among other things. The topic used to be called "metamathematics". An old fashioned intro class would usually build up the machinery to prove Gödel's incompleteness theorem, do a little model theory, maybe some set theory, etc. I think a lower level discrete math class wouldn't touch any of this.

See: https://en.wikipedia.org/wiki/Mathematical_logic

There are prerequisites:

https://ocw.mit.edu/courses/mathematics/18-404j-theory-of-co...

> 6.042J Mathematics for Computer Science

> 18.200 Principles of Discrete Applied Mathematics

And, prerequisites for the above prerequisites:

https://ocw.mit.edu/courses/mathematics/18-01sc-single-varia...

> 18.01 Single Variable Calculus

https://ocw.mit.edu/courses/mathematics/18-310-principles-of...

> 18.02 Multivariable Calculus

Overall, you need to have a thorough understanding of high-school math (12th grade), which is not unreasonable.

I don't remember needing anything except Discrete Maths when I took this course in the Uni, so I think multivariate calculus is overkill.

Judging by his (excellent) textbook mostly basic familiarity with math logic and proofs should be enough. Calculus helps as a first example of proof technique application but should not be a necessity.

In fact, I went through most of his book on my own - my own electrical engineering degree was enough to follow and solve exercises.

To do Big O, you'll need L'Hopitals rule. And, rates of change in general.

Well, the author does a great job of giving intuitive explanations for things not covered throughly in the book.

Besides, rate of change is high school material: physics and last year math lessons do cover it.

At least in eastern europe they do.

I'm a math prof in the US. Here, I don't find that "physics and last year math lessons do cover it." If they do where you are, I'm envious.

The explanation was shallow at best, omitting key definitions, coming up with Newton-style "infinitesmall" hand waiving.

They mostly made sure we were familiar with relevant notation. This somewhat helped in early uni physics-related courses, until calculus caught up.

That was in a math school back in post-soviet lithuania, so russian approach to math schooling implied.

Btw, as much as I know, basic set theory, math logic and proof techniques (e.g. "How to prove it" level roughly) are almost universally delayed till university years. These generic tools are much more important than calculus!

I don't really understand why. This results in many omissions in school-level curriculum, I.e giving formulas with no proofs. This results in kids seeing math as a kind of meaningless and boring symbol manipulation.

Was there ever a discussion around this problem in the US?

Sipser’s theory of computation book is one of the best examples of technical exposition I’ve ever seen.

Yes. Fantastic textbook.

I found it to be incomplete or wrong at some places. And Introduction to Automata theory, languages, and computation to be a better exposition.

I think it is cool to contrast Sipser's course with a more "modern" take by Mihai Pătraşcu [1] [2].

[1] https://infoweekly.blogspot.com/2009/02/teaching.html

[2] https://inst.eecs.berkeley.edu/~cs172/sp09/

Interesting, thank you for the links. This version does not seem to have taken off, though. (The links are from 09.)

I took ToC about a year ago, as the final required course in my PhD studies, and we used Sipser’s text although the professor also wandered off into the arithmetic hierarchy which he doesn’t cover.

I will absolutely credit the course with igniting an intense curiosity in the foundations of computing (and of mathematics in general) but I agree that it’s time for a more modern approach.

Those criticisms are definitely common these days: lots of Sipser-style material is not very relevant or pedagogically compelling. I think push-down automata are a great example that many people would be happy to skip.

On the other hand, that choice of topics is pretty idiosyncratic. There are a lot of big concepts, some pretty tangential, that are covered very briefly and could easily be skipped. So I don't think that exact course is a good outline for a new canon. But I agree with the premise for sure.

I'm fortunate enough to have taken the TOC course by Sipser in person. High clarity despite the arcane nature of the materials. Quite some amusement as well (not sure if it's the case in the ocw course). Highly recommended.

I so hated that stuff when it was a requisite in uni. Happen to open the book just 2 days ago after almost 10y , what a coincidence. Now I love this stuff, it's truly timeless.

Something or the other is obsure about this task. But to be honest I'd have never come across something as ridiculous and what is purported to be true here. My ability to write useless stuff is unprecedented and unmatched. This is how I operate. This is how the dice rolls and how it always lands on an eight or a double-six. That's life for you.

For people who are planning to go through this course. What are your motivations for doing so?

Something or the other does stick and prosper. Intentions are rarely misunderstood or misguided. At best there is weird discrepancy between what is thought and what is revealed. What I'm saying is strange and may even be out of context I know but this shouldn't be taken as evidence of non-chalance.

For a comprehensive overview of computation on a foundational level, see Feynman's lectures on computation:

https://theswissbay.ch/pdf/Gentoomen%20Library/Extra/Richard...

I've been implementing the flip flop gates using SICP wires:

https://mitpress.mit.edu/sites/default/files/sicp/full-text/...

It was neat seeing the concept of "feedback" (logic gate output gets fed in as an input) then seeing it actually work in the SICP simulator. It immediately went into an infinite loop, but that's correct behavior. The solution was to add a clock line (a wire which goes 0 to 1 and back to 0 over a specific time interval), then update the simulation until the clock line changes. Presto, I had my own flip flops.

Ended up implementing some shift registers (thanks to Feynman). Lots of fun, and it clarifies the concept of a "cycle" -- I found it really hard to understand what a "cycle" actually meant till implementing the gates.

The reversible computation is cool: NOT, Controlled NOT (CN), and Controlled Controlled NOT (CCN) gives you everything you need to make a reversible universal computer.

It turns out that reversible computation is far more energy efficient than normal computation. You can understand with an analogy. Think of a pool table. Imagine the cue ball hitting the 8 ball. When the cue ball is in motion (and ignoring friction), then no energy needs to be spent -- it's already in motion, so you don't need to do anything to cause the situation to "keep going". It just keeps going on its own.

When the cue ball hits the 8 ball, part of that energy is transferred. In the ideal case, the cue ball stops moving and the 8 ball starts at the same speed.

By arranging pool balls in specific ways, you can mimic an AND gate and an OR gate. The outputs are the directions that the balls end up going. And the truth table for AND and OR is simple, so you just need to represent the truth table using "directions" instead of volts.

If you have two inputs, you'll want two outputs, because otherwise you need to stop a ball entirely (energy is lost) which is very costly in comparison. The best outcome is for the second ball to carry along the energy of the second input, even though you don't directly need the answer just to represent AND or OR gates.

The result is that you can run the simulation, and then reverse the entire thing to get back your original inputs. :)

Wow, Feynman's explanation of the halting problem is thorough yet concise in his usual amazing fashion. Many thanks for linking that book!

Reply on news.ycombinator.com