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 contradiction assume contrapositve tic-tac-toe cases clever natural counterexample exist rigor proof problem root thing men numbers partners balls face claim problems card triangle times kind point things half 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 string epsilon guessing statement answer problem input algorithm godel completeness consistency searches theorem computation prove air negation programs contradiction 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 proof theorem problem statements godel contradiction machines negation systems stuff incompleteness distinction parallel tuple things turing programs language hilbert 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 rules proof axioms inference statements proofs contradiction reasoning thing systems hilbert 30s bit answer algorithm string kind negation properties From David Doty 0 likes 31 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 halts catch-22 programs inputs source problem table contradiction proof string rows coder diagonalization kind subroutine algorithm problems class output From David Doty 0 likes 60 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 programs language programming interpreter source output return javascript universality notion words matter contradiction runs v0 returns symbol question task 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 algorithm string source diagonalization halts argument inputs object loop loops programs opposite function definition contradiction problem diagonal row kth From David Doty 0 likes 268 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 epsilon algorithm halts problem string machine turing property thing contradiction behavior step age dancer ar dmd tm boilerplate rest From David Doty 0 likes 193 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 input string inputs algorithm halts m. behavior problem machine tm answer function contradiction turing language algorithms definition lot difference From David Doty 0 likes 513 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 algorithm string epsilon halts tm a. w. words contradiction problem definition loops function object m. inputs machine turing kind From David Doty 0 likes 326 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 epsilon algorithm halts problem function string machine w. contradiction turing point thing inputs python paltz sense behavior constants answer From David Doty 0 likes 409 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 string zeros blocks language words copies region pumping strings lemma contradiction bit substring half xyz p. form symbols direction From David Doty 1 likes 263 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 language string copies contradiction minus length copy xyz strings l. note p. beginning lemma pumping reasoning run key thing From David Doty 1 likes 90 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 prime string l. lemma w. b. copy lengths strings contradiction zeros symbol fact languages animal hook y. xyz cancel From David Doty 1 likes 72 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 star lemma operations zeros expression intersection languages closure contradiction numbers transition strings operation proof properties bit From David Doty 1 likes 77 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 zeros language length symbols strings p. dfa boilerplate b. string pumping condition thing piece contradiction proof idea bit lot From David Doty 1 likes 298 plays 0