Talks
Speakers
Events
Topics
Sign in
Home
Talks
Speakers
Events
Topics
Leaderboard
Use
Analytics
Sign in
Suggest modification to this talk
Title
Description
Every aspect of our lives has been transformed by the invention of general-purpose programmable computers. As a result, it's tempting to believe that computers can solve any logical or mathematical problem; that if we throw enough time, money and nerds at a question, we can produce a program which answers it. Unfortunately the universe is never that convenient. There are hard theoretical limits on what programs are capable of doing, and there will always be straightforward problems which are impossible for any computer to solve. This talk uses Ruby to tell a nail-biting, math-free story about the source of a computer's power, the inevitable drawbacks of that power, and the impossible programs which lie at the heart of uncomputability. Help us caption & translate this video! http://amara.org/v/FG7p/
Date
Summarized using AI?
If this talk's summary was generated by AI, please check this box. A "Summarized using AI" badge will be displayed in the summary tab to indicate that the summary was generated using AI.
Show "Summarized using AI" badge on summary page
Summary
Markdown supported
The video titled "Impossible Programs" features speaker Tom Stuart, who discusses the theoretical limits of what computers can accomplish, particularly focusing on the concept of uncomputability. This talk emphasizes that while computers are powerful and can execute a wide range of tasks through universal programming languages like Ruby, they are nonetheless constrained by inherent limitations. Key points covered in the talk include: - **Universal Systems**: Computers can simulate one another using different programming languages, highlighting their Turing completeness. This implies that any well-defined computational task can theoretically be performed by any universal system. - **Programs as Data**: Programs can be conceptualized as data, allowing for the construction of interpreters within these languages. For example, a Ruby program can be designed to read and evaluate other Ruby programs. - **Self-Evaluating Programs**: The construction of programs that evaluate themselves leads to paradoxes, particularly in attempts to determine their own outputs. An example discussed is a self-referencing program that leads to infinite loops due to contradictory outputs. - **The Halting Problem**: The core challenge illustrated is the halting problem — the impossibility of creating a program that can determine whether any arbitrary program will halt or run indefinitely. This ties into Rice’s Theorem, which states that any interesting behavioral property of a program is undecidable. - **Implications for Programming**: The talk stresses that despite the ability to create complex software, verifying their correctness or predicting their behavior under all conditions remains an insurmountable challenge. - **Practical Approaches**: Suggestions include running programs for time-limited evaluations and employing smaller, manageable tests to check for specific behaviors, rather than attempting to solve broader, undecidable properties entirely. In conclusion, Tom Stuart encourages a deeper exploration of these concepts, advocating for his book on applying Ruby to understand complex topics like Turing machines and type systems. The discussion serves to highlight the fascinating yet frustrating interplay between computational power and its limitations.
Suggest modifications
Cancel
