Theory of Computation

[Genady]

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. 

[SuperSlim]

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.

[Genady]

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.

[SuperSlim]

Ka-ching!

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

[Genady]

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.

[SuperSlim]

8 minutes ago, Genady said:

It is not about information.

What isn't?

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

[Genady]

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.

[SuperSlim]

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.

[Genady]

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.

[SuperSlim]

On 3/13/2022 at 3:01 PM, Genady said:

Yes, its role is trivial.

It doesn't play a non-trivial role.

Sort of how numbers play a trivial role in arithmetic, huh?

[Genady]

2 hours ago, SuperSlim said:

Sort of how numbers play a trivial role in arithmetic, huh?

No.

[studiot]

On 3/13/2022 at 2:01 AM, Genady said:

Yes, its role is trivial.

It doesn't play a non-trivial role.

+1 for more patience than I have.

[Genady]

28 minutes ago, studiot said:

+1 for more patience than I have.

Thank you.

Only until they start using a foul language.

[studiot]

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.

[Genady]

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.