u/tauloverin r/compsci • Recommends
Gödel's First Incompleteness Theorem, proof sketch using Halting Problem (video)
0:00 / 0:00
#godel'sfirstincompletenesstheorem#haltingproblem#turingmachines
Gödel's First Incompleteness Theorem, Proof Sketch
Undefined Behavior
29K subscribers • 9 videos on Hallway
- Recommended by 1 person: 1 in engineering communities.
- Presented by Cory Chang
- Linked in the descriptionSlides on cs.cmu.edu
Intermediate. Assumes working knowledge.
64K views9 years ago1 recommendation
Computer scienceComputation and complexityAlgorithms
Cory Chang presents a proof sketch of Gödel's first incompleteness theorem using the halting problem.
Kurt Gödel rocked the mathematical world with his incompleteness theorems. With the halting problems, these proofs are made easy! Created by: Cory Chang Produced by: Vivian Liu Script Editor: Justin Chen Special thanks to Ryan O’Donnell, associate professor at Carnegie Mellon University (cs.cmu.edu/~odonnell/). Twitter: twitter.com/UBehavior — Extra Resources: Ryan O’Donnell’s slide deck: cs.cmu.edu/~aada/courses/15251s16/www/slides/15251-s16-lectu… Wikipedia entry: en.wikipedia.org/wiki/Gödel's_incompleteness_theorems Rules of deductive calculus: en.wikipedia.org/wiki/Hilbert_system Proof that square root of 2 is irrational, in Metamath: us.metamath.org/mpegif/sqr2irr.html Mizar system: mizar.org Metamath: us.metamath.org/index.html Playlist to previous videos: youtube.com/playlist?list=PLlwsleWT767dwRXyAyL0-63ON6cCOXY8EWhy it's here
1 person recommends thisWhat people say. Recommended as an intuitive proof sketch of Gödel's first theorem using computer science concepts.