Search for tag: "contradiction"

18 Media

ECS20 - W22 - Lecture 5 (3T): Proofs duration 1 hour 21 minutes ECS20 - W22 - Lecture 5 (3T): Proofs ECS20 - W22 - Lecture 5 (3T): Proofs	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… proofs +28 More From Phil Rogaway 0 likes 134 plays 0
ECS 220 6c:7.2-4 Gödel’s… duration 5 minutes 26 seconds ECS 220 6c:7.2-4 Gödel’s… ECS 220 6c:7.2-4 Gödel’s Incompleteness Theorem (consistency)	ECS 220 6c:7.2-4 Gödel’s Incompleteness Theorem (consistency) proof +19 More From David Doty 0 likes 25 plays 0
ECS 220 6c:7.2-3 Gödel’s… duration 6 minutes 36 seconds ECS 220 6c:7.2-3 Gödel’s… ECS 220 6c:7.2-3 Gödel’s Incompleteness Theorem (soundness)	ECS 220 6c:7.2-3 Gödel’s Incompleteness Theorem (soundness) statement +19 More From David Doty 0 likes 30 plays 0
ECS 220 6c:7.2-2 From undecidable problems to… duration 5 minutes 55 seconds ECS 220 6c:7.2-2 From undecidable problems to… ECS 220 6c:7.2-2 From undecidable problems to unprovable truths	ECS 220 6c:7.2-2 From undecidable problems to unprovable truths statement +19 More From David Doty 0 likes 32 plays 0
ECS 220 6b:7.2-1 halting problem duration 6 minutes 0 seconds ECS 220 6b:7.2-1 halting problem ECS 220 6b:7.2-1 halting problem	ECS 220 6b:7.2-1 halting problem input +19 More From David Doty 0 likes 62 plays 0
ECS 220 6a:7.2-1 programming languages with… duration 3 minutes 8 seconds ECS 220 6a:7.2-1 programming languages with… ECS 220 6a:7.2-1 programming languages with interpreters have non-halting programs	ECS 220 6a:7.2-1 programming languages with interpreters have non-halting programs input +19 More From David Doty 0 likes 46 plays 0
ECS 120 10b:3 diagonalization to show the halting… duration 9 minutes 9 seconds ECS 120 10b:3 diagonalization to show the halting… ECS 120 10b:3 diagonalization to show the halting problem is undecidable	ECS 120 10b:3 diagonalization to show the halting problem is undecidable input +19 More From David Doty 0 likes 295 plays 0
ECS 120 9b:3 rejecting problem is undecidable duration 6 minutes 47 seconds ECS 120 9b:3 rejecting problem is undecidable ECS 120 9b:3 rejecting problem is undecidable	ECS 120 9b:3 rejecting problem is undecidable input +19 More From David Doty 0 likes 195 plays 0
ECS 120 9b:2 empty language problem is undecidable duration 7 minutes 38 seconds ECS 120 9b:2 empty language problem is undecidable ECS 120 9b:2 empty language problem is undecidable	ECS 120 9b:2 empty language problem is undecidable epsilon +19 More From David Doty 0 likes 545 plays 0
ECS 120 9b:1 acceptance problem is undecidable duration 8 minutes 28 seconds ECS 120 9b:1 acceptance problem is undecidable ECS 120 9b:1 acceptance problem is undecidable	ECS 120 9b:1 acceptance problem is undecidable input +19 More From David Doty 0 likes 330 plays 0
ECS 120 9a:3 no-input halting problem is… duration 15 minutes 57 seconds ECS 120 9a:3 no-input halting problem is… ECS 120 9a:3 no-input halting problem is undecidable	ECS 120 9a:3 no-input halting problem is undecidable input +19 More From David Doty 0 likes 425 plays 0
ECS 120 5b:9 pumping lemma proof that (01)n(10)n… duration 8 minutes 0 seconds ECS 120 5b:9 pumping lemma proof that (01)n(10)n… ECS 120 5b:9 pumping lemma proof that (01)n(10)n is not regular	ECS 120 5b:9 pumping lemma proof that (01)n(10)n is not regular length +19 More From David Doty 1 likes 302 plays 0
ECS 120 5b:8 pumping lemma proof that 0i1j is not… duration 3 minutes 35 seconds ECS 120 5b:8 pumping lemma proof that 0i1j is not… ECS 120 5b:8 pumping lemma proof that 0i1j is not regular	ECS 120 5b:8 pumping lemma proof that 0i1j is not regular zeros +19 More From David Doty 1 likes 99 plays 0
ECS 120 5b:7 pumping lemma proof that 1n2 is not… duration 5 minutes 7 seconds ECS 120 5b:7 pumping lemma proof that 1n2 is not… ECS 120 5b:7 pumping lemma proof that 1n2 is not regular	ECS 120 5b:7 pumping lemma proof that 1n2 is not regular length +19 More From David Doty 1 likes 75 plays 0
ECS 120 5b:5 closure properties proof that equal… duration 2 minutes 31 seconds ECS 120 5b:5 closure properties proof that equal… ECS 120 5b:5 closure properties proof that equal zero-one is not regular	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:… language +16 More From David Doty 1 likes 79 plays 0
ECS 120 5b:2 pumping lemma proof that 0n1n is not… duration 7 minutes 43 seconds ECS 120 5b:2 pumping lemma proof that 0n1n is not… ECS 120 5b:2 pumping lemma proof that 0n1n is not regular	ECS 120 5b:2 pumping lemma proof that 0n1n is not regular lemma +19 More From David Doty 1 likes 339 plays 0