Problém zastavení, PCP, (Ne)rozhodnutelné problémy o CFG
Section outline
-
-
Students mustMark as done
13. video přednáška Nerozhodnutelné problémy
Důkazy propojují myšlenky dohromady, doporučuji shlédnout celé. To co bych ráda, abyste z přednášky znali, je v náledujcících minutách:
0-7:00
Nerozhodnutelné problémy, redukce problému
12:45-22:46
Problém zastavení (Halting problém), Postův korespondenční problém (PCP)
1:01:14-1:25:17
Věta: PCP je nerozhodnutelný. (důkaz před tím přeskočen)
Rozhodnutelné a nerozhodnutelné problémy pro bezkontextové gramatiky.
-