L11: Church-Turing Thesis and Examples of Decidable Languages

Church-Turing thesis; examples of decidable languages. An algorithm is defined by the existence of a TM that implements the algorithm. One of Turing's great contributions is in formally defining what an algorithm is.

[@MrDanielphillis]

my new favorite TV show - thanks mate !

[@hamedminaee]

The best video in the subject of Church-Turing Thesis

[@warnford]

this is great - thank you so much. Sipser takes a bit of reading, and these lectures really are wonderful. ( written on Mueller Day)

[@warnford]

Good lecture on Church Turing - from a very modern point of view - everyone knows what a computer is now whereas twenty or thirty years ago they were just ideas. Loved the illusion at 50 mins that the professor rested them on stuff he hadnt covered. Some problems never change ! ( struggling with that in my own course)

[@aydinahmadli7005]

thank you, it is solid explanation

[@RoyalQNY]

Ahh, so this is Jeff Ross' day job... You gotta do something other than attend Comedy Central roasts once a year..

[@danielmarzec3743]

EQ_CFG is actually not decidable according to Sipser 3rd Edition pg 200.

[@coop4476]

Because CFG is not closed under intersection nor under complement.

[@luizfernandoafrabrito8473]

The last example of decidable language is wrong. In fact A_cfg is decidable but we need to find another method since a context-free language is not closed under complemention or intersection.

[@dishendra.]

1:08:20

[@maheshg3619]

Check out 8:55 Theoritical physicist making fun of Turing machines

[@TheNsn666]

GOD told me that P=NP, he is the prove.