Search for tag: "contradiction"

ECS20 - W22 - Lecture 5 (3T): Proofs

Online lecture from 1/19/2022. Sundry proofs, chosen to illustrate recurring ideas and themes. I had prepared 11 examples, and we got through 8 of them. Also included some general comments on…

From  Phil Rogaway 0 likes 132 plays 0  

ECS 220 6c:7.2-4 Gödel’s Incompleteness Theorem (consistency)

From  David Doty 0 likes 18 plays 0  

ECS 220 6c:7.2-3 Gödel’s Incompleteness Theorem (soundness)

From  David Doty 0 likes 22 plays 0  

ECS 220 6c:7.2-2 From undecidable problems to unprovable truths

From  David Doty 0 likes 22 plays 0  

ECS 220 6b:7.2-1 halting problem

From  David Doty 0 likes 44 plays 0  

ECS 220 6a:7.2-1 programming languages with interpreters have non-halting programs

From  David Doty 0 likes 33 plays 0  

ECS 120 10b:3 diagonalization to show the halting problem is undecidable

From  David Doty 0 likes 191 plays 0  

ECS 120 9b:3 rejecting problem is undecidable

From  David Doty 0 likes 161 plays 0  

ECS 120 9b:2 empty language problem is undecidable

From  David Doty 0 likes 395 plays 0  

ECS 120 9b:1 acceptance problem is undecidable

From  David Doty 0 likes 272 plays 0  

ECS 120 9a:3 no-input halting problem is undecidable

From  David Doty 0 likes 317 plays 0  

ECS 120 5b:9 pumping lemma proof that (01)n(10)n is not regular

From  David Doty 1 likes 188 plays 0  

ECS 120 5b:8 pumping lemma proof that 0i1j is not regular

From  David Doty 1 likes 74 plays 0  

ECS 120 5b:7 pumping lemma proof that 1n2 is not regular

From  David Doty 1 likes 67 plays 0  

ECS 120 5b:5 closure properties proof that equal zero-one is not regular

This is presenting the same material as in this alternate lecture, but I give more intuition in the alternate lecture:…

From  David Doty 1 likes 73 plays 0  

ECS 120 5b:2 pumping lemma proof that 0n1n is not regular

From  David Doty 1 likes 236 plays 0