Impossible Programs

by Tom Stuart

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.

00:00:20.720 I'd like to introduce Tom Stuart from London. He's been doing Ruby for nine years and is a former Bay Area resident who lived here in '99. He then moved to London, and this is now his triumphant return. Tom is the recent author of 'Understanding Computation.' He was a guest on the Ruby Rogues podcast to discuss his book in episode 120, which blew all of our minds. Anyway, let's give a big hand for Tom and his talk on Impossible Programs.

00:01:02.879 Cool! Thanks, Josh. Hi everyone, thank you very much for coming to this talk. Today, I'm going to discuss some impossible programs.

00:01:09.360 So, how can a program be impossible? What does it mean for a program to be impossible? I will explain this by reminding you of two facts of life. The first fact is that we collectively demand universal systems. What do I mean by universal systems? Well, I'm sure it's obvious to you that you could take any Python program and translate it into Ruby.

00:01:21.600 You could walk through the program and replace each piece of Python syntax with Ruby syntax. By the time you’re done, you will have a Ruby program that does the same thing as the original Python program. The fact that you're able to do this doesn't necessarily mean that Ruby is a super awesome programming language, even though it is. It simply indicates that these programming languages share the same kind of power.

00:02:02.960 You can do the reverse as well; nothing special about Ruby here. You could take a Ruby program and translate it into Python. Moreover, it's possible to write a single Ruby program that is equivalent to all Python programs. What I mean by this is that you can implement a Python interpreter in Ruby. You write this single Ruby program, and you're done. You can then feed it a Python program as data, and it will function according to the data it receives without needing to change the Ruby code itself.

00:03:00.879 Again, there's nothing unique about Ruby or the combination of Ruby and Python. You could implement a JavaScript interpreter in Ruby, or a Ruby interpreter in JavaScript. There’s a whole constellation of these systems that we refer to as universal systems. Any of these systems can simulate any other, exhibiting a special relationship.

00:03:19.360 Some people refer to this property as Turing completeness. Why are we so interested in universal systems? The essential characteristic of universal systems is their ability to run software. When you create one, you essentially create a machine that can behave differently depending on the data fed to it. We don't just want machines to simply do work for us; we want general-purpose machines that we can design and then feed data to, allowing them to perform any job based on the data.

00:03:38.879 MRI is one such general-purpose machine. It is a C program that you can download onto your computer. Although it's just a single program, it can perform a wide range of tasks depending on the input data. So that's the first fact of life: we want these universal systems for general-purpose machines. The second fact is that programs are data. This is rather obvious.

00:04:09.360 When you enter a program in IRB and execute it, you think of it as a series of instructions. However, it's also possible to view it as a string. Ruby understands strings. I could save that program as a string, inside which exists a program as data. This observation might seem mundane, but the implications are quite profound.

00:05:06.400 Every program can be represented as a string, and strings are simply sequences of bytes. I could break down that string into bytes, effectively representing the original program in a different format. This can be seen as converting a giant binary number into a giant decimal number, meaning that the Ruby program you write, such as 'Hello, World!', is just a representation of a specific number in a different context.

00:06:11.919 These facts lead us to an inescapable conclusion: some programs written for these universal systems inevitably contain infinite loops, and the connection might not be obvious at first. To clarify, every universal system can simulate every other universal system, including itself.

00:06:49.120 It follows that every universal programming language can implement its own interpreter. If all we know about Ruby is that it's a universal system, we must be able to write a method in Ruby to evaluate Ruby programs. This isn't merely a theoretical exercise; you can read in a string, parse it, and evaluate it. In Ruby, this is straightforward as it has an eval method.

00:07:56.800 Even if Ruby didn't have eval, you could still implement this functionality manually. The evaluate method would check if a string from standard input reads correctly. For example, consider evaluating a program that reverses a string. The evaluation asks: if I run this program, what will its output be?

00:09:01.839 If we can write an evaluate method in Ruby, then we can also write a method that evaluates itself. It would take a single argument and evaluate itself. Therefore, if you provide this method with the program itself, it will output the program reversed, as that's what this self-evaluating program does.

00:10:05.040 Now, if we further construct a program that evaluates its own execution resulting in 'no', it will output 'yes.' This program, which I’ll refer to as does_it_say_no.rb, reads in a program, evaluates it against its own source code, and checks if the output is the literal string 'no.' This entire process seems logical on the surface.

00:11:03.839 However, if we feed this program into itself, what could happen? It could output 'yes' or 'no'. The question this program seeks to answer is whether it outputs 'no' when fed its own code. If it outputs 'yes', it's incorrect, as that means it didn't say 'no'. If it outputs 'no', that means it did say 'no', which is also incorrect. Hence, neither option is valid.

00:12:30.639 The only logical outcome is that this program loops indefinitely, never reaching a conclusion. Consequently, if Ruby is a universal system, you can write the evaluate method, which allows the creation of a never-ending loop program. While it may seem trivial to create infinite loops, the real challenge lies in the implications—certain programs cannot be evaluated correctly, leading to this conclusion.

00:13:45.440 An almost paradoxical situation arises: you must analyze this hypothetical program and come to the conclusion that while it appears we can find solutions through Ruby, the existence of an interpreter suggests unexpected limitations. In essence, the existence of universal systems means that writing a Rust interpreter in Rust would yield similar issues.

00:14:58.880 To summarize, in Ruby, we can create programs that exhibit well-defined behaviors and those that loop infinitely—two specific cases with predictable finishes. But can we construct a Ruby program that will reliably determine if any arbitrary Ruby program will halt? This question is known as the halting problem.

00:16:38.240 Let’s explore a few examples to gain insights into the complexity of the halting problem. For instance, a program that reads a string and outputs the same string after replacement may seem straightforward. After reflection, however, the actual process relays on an in-depth understanding of Ruby's semantics, making it non-trivial.

00:18:15.440 Consider also a program that checks the Goldbach conjecture, which states that every even number can be expressed as the sum of two primes. The complexity of determining whether this program halts is harder. Despite checking a vast number of cases, we still lack definitive proof. Writing a Ruby program to ascertain this fact seems overwhelming and likely impossible.

00:20:05.119 What’s crucial here is that if you could construct a reliable evaluation function against halting, it necessitates a layer of abstraction that goes beyond efficient execution. However, any system robust enough to analyze itself faces inherent limitations.

00:21:37.680 So, why should we care about this? This realization suggests we cannot merely ask whether any given program halts or meets certain specifications. In programming, we regularly question whether code functions correctly or if it will encounter infinite loops, but concretely confirming the expected outcomes proves elusive.

00:23:20.040 Rice's Theorem characterizes this challenge: any interesting property about a program’s behavior is undecidable. Although we can inspect functional properties like whether the code contains a particular string, assessing runtime behavior—what happens when executed—remains inherently beyond our grasp.

00:24:56.159 The fundamental issue revolves around prediction, as we must run a program to know its behavior. Hence, unless we can abstract away details or restrict ourselves to decidable questions, we face insurmountable obstacles regarding verification and judgment.

00:26:18.240 Nonetheless, there are strategies we can adopt. First, if faced with a question we can't resolve in reasonable time, we can simply run the program for a limited period and decide whether to continue. Additionally, approaching the challenge through smaller, manageable questions enables testing portions of code rather than entire specifications.

00:27:57.440 Furthermore, compilers apply methods such as unreachable code elimination to manage undecidable properties, although they cannot fully guarantee coverage. Ultimately, converting statements into an approximate version allows for easier questions about behavior without requiring unique references, striking a balance between complexity and practical resolution.

00:29:55.520 In conclusion, if you're interested in exploring this subject further, I've written a book on applying Ruby to understand concepts like Turing machines, halting problems, type systems, and interpreters. Thank you for your attention!