Jump to content

Theory of Computation


Genady

Recommended Posts

Just now, SuperSlim said:

Does it have a good explanation of Shannon entropy? It might not because Shannon entropy is about communicating information, not computing it.

Or correct me if I'm mistaken.

You are not mistaken. It didn't touch Shannon entropy yet, and I don't expect it to do so.

Link to comment
Share on other sites

8 minutes ago, SuperSlim said:

Ka-ching!

I should say, communication of information is about preserving it. Computation, well, just isn't. It can be logically reversible, however.

It is not about information.

Link to comment
Share on other sites

1 minute ago, SuperSlim said:

What isn't?

Are you saying MIT's theory of computation online course isn't "about" information?

I'm saying that the concept of information doesn't play a role in the theory taught in this course.

BTW, it is not an online course. It is a recording from the MIT class, just like all other MIT OCW courses.

Link to comment
Share on other sites

49 minutes ago, Genady said:

I'm saying that the concept of information doesn't play a role in the theory taught in this course.

Ok then. Well I'm saying that's a bit of a misconception. Actually it's a pretty big one.

I would say there is no theory of computation in which information doesn't "play a role". I say that because any device that can reasonably be called a computer, has to process physical information. It's also because computer engineers who design and build computers have to decide how to measure outputs, and how the information is physically represented as the computer processes it.

 

I mean, how did it occur to you that computational theory doesn't include the concept of information? It does include it. MIT professors who put the course together might assume that students already know this (almost trivial) thing. I know I do.

Link to comment
Share on other sites

13 minutes ago, SuperSlim said:

Ok then. Well I'm saying that's a bit of a misconception. Actually it's a pretty big one.

I would say there is no theory of computation in which information doesn't "play a role". I say that because any device that can reasonably be called a computer, has to process physical information. It's also because computer engineers who design and build computers have to decide how to measure outputs, and how the information is physically represented as the computer processes it.

 

I mean, how did it occur to you that computational theory doesn't include the concept of information? It does include it. MIT professors who put the course together might assume that students already know this (almost trivial) thing. I know I do.

Yes, its role is trivial.

It doesn't play a non-trivial role.

Link to comment
Share on other sites

On 3/12/2022 at 12:26 PM, Genady said:

MIT OCW has recently uploaded a new complete set of video lectures from this class:

Theory of Computation | Mathematics | MIT OpenCourseWare

I am 25% through and enjoying it. 

What would be really useful would be a summary of what the course is actually about since 'computation' means different things to different sections of the maths community.

That would be useful to others (like me) who might actually be thinking of looking at it.

Thanks.

Link to comment
Share on other sites

34 minutes ago, studiot said:

What would be really useful would be a summary of what the course is actually about since 'computation' means different things to different sections of the maths community.

That would be useful to others (like me) who might actually be thinking of looking at it.

Thanks.

You're right, I should've done it in the OP. Here it is, from the horse's mouth:

Quote

Course Description

This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

Course Outline

  • Automata and Language Theory (2 weeks)
    • Finite automata, regular expressions, push-down automata, context-free grammars, pumping lemmas.
  • Computability Theory (3 weeks)
    • Turing machines, the Church-Turing thesis, decidability, the halting problem, reducibility, the recursion theorem.
  • Complexity Theory (7 weeks)
    • Time and space measures of complexity, complexity classes P, NP, L, NL, PSPACE, BPP and IP, complete problems, the P versus NP conjecture, quantifiers and games, hierarchy theorems, provably hard problems, relativized computation and oracles, probabilistic computation, interactive proof systems.

Since at the time MIT campus was shut down due to Covid, the course lectures are recorded from Zoom sessions.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.