Search for tag: "contradiction"

18 Media

01:21:36 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 132 plays 0
05:26 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 18 plays 0
06:36 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 22 plays 0
05:55 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 22 plays 0
06:00 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 44 plays 0
03:08 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 33 plays 0
09:09 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 191 plays 0
06:47 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 161 plays 0
07:38 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 395 plays 0
08:28 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 272 plays 0
15:57 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 317 plays 0
08:00 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 188 plays 0
03:35 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 74 plays 0
05:07 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 67 plays 0
02:31 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 73 plays 0
07:43 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 236 plays 0