What, generally speaking, can we do with universal systems like Turing machines, the lambda calculus, and partial recursive functions? If we can properly understand the capabilities of these systems, then we’ll be able to investigate their limitations.

The practical purpose of a computing machine is to perform algorithms. An algorithm is a list of instructions describing some process for turning an input value into an output value, as long as those instructions fulfill certain criteria:

For example, one of the oldest known algorithms is Euclid’s algorithm, which dates from around 300 BC. It takes two positive integers and returns the largest integer that will divide them both exactly—their greatest common divisor. Here are its instructions:

We’re happy to recognize this as an algorithm, because it appears to meet the basic criteria. It only contains a few instructions, and they all seem simple enough to be performed with pencil and paper by someone who doesn’t have any special insight into the overall problem. With a bit of thought, we can also see that it must finish within a finite number of steps for any input: every repetition of step 3 causes one of the two numbers to get smaller, so they must eventually reach the same value^[64] and cause the algorithm to finish. It’s not quite so obvious that it’ll always give the correct answer, but a few lines of elementary algebra are enough to show that the result must always be the greatest common divisor of the original numbers.

So Euclid’s algorithm is worthy of its name, but like any algorithm, it’s just a collection of ideas expressed as human-readable words and symbols. If we want to do something useful with it—maybe we’d like to explore its mathematical properties, or design a machine that performs it automatically—we need to translate the algorithm into a stricter, less ambiguous form that’s suitable for mathematical analysis or mechanical execution.

We already have several models of computation that we could use for this: we could try to write down Euclid’s algorithm as a Turing machine rulebook, or a lambda calculus expression, or a partial recursive function definition, but all of those would involve a lot of housekeeping and other uninteresting detail. For the moment, let’s just translate it into unrestricted Ruby:^[65]

def euclid(x, y)
  until x == y
    if x > y
      x = x - y
    else
      y = y - x
    end
  end

  x
end

This #euclid method contains essentially the same instructions as the natural language description of Euclid’s algorithm, but this time, they’re written in a way that has a strictly defined meaning (according to the operational semantics of Ruby) and therefore can be interpreted by a machine:

>> euclid(18, 12)
=> 6
>> euclid(867, 5309)
=> 1

In this specific case, it’s been easy to take an informal, human-readable description of an algorithm and turn it into unambiguous instructions for a machine to follow. Having Euclid’s algorithm in a machine-readable form is very convenient; now we can perform it quickly, repeatedly, and reliably without having to employ manual labor.

This raises an important question: can any algorithm be turned into instructions suitable for execution by a machine? Superficially that seems like a trivial thing to ask—it was pretty obvious how to turn Euclid’s algorithm into a program, and as programmers, we have a natural tendency to think of the two things as interchangeable—but there’s a real difference between the abstract, intuitive idea of an algorithm and the concrete, logical implementation of that algorithm within a computational system. Could there ever be an algorithm so large, complex, and unusual that its essence can’t be captured by an unthinking mechanical process?

Ultimately there can be no rigorous answer, because the question is philosophical rather than scientific. The instructions of an algorithm must be “simple” and “without ingenuity” so that it “can be performed by a person,” but those are imprecise ideas about human intuition and capability, not mathematical assertions of the kind that can be used to prove or disprove a hypothesis.

We can still collect evidence one way or the other by coming up with lots of algorithms and seeing whether our computing system of choice—Turing machines, or lambda calculus, or partial recursive functions, or Ruby—can implement them. Mathematicians and computer scientists have been doing exactly that since the 1930s, and so far, nobody has managed to devise a reasonable algorithm that can’t be performed by these systems, so we can be pretty confident about our empirical hunch: it certainly looks as though a machine can perform any algorithm.

Another strong piece of evidence is the fact that most of these systems were developed independently as attempts to capture and analyze the informal idea of an algorithm, and were only later found to be exactly equivalent to each other. Every historical attempt to model the idea of an algorithm has produced a system whose capabilities are identical to those of a Turing machine, and that’s a pretty good hint that a Turing machine adequately represents what an algorithm can do.

The idea that any algorithm can be performed by a machine—specifically a deterministic Turing machine—is called the Church–Turing thesis, and although it’s just a conjecture rather than a proven fact, it has enough evidence in its favor to be generally accepted as true.

The Church–Turing thesis implies that Turing machines, despite their simplicity, have all the power required to perform any computation that can in principle be carried out by a person following simple instructions. Many people go further than this and claim that, since all attempts to codify algorithms have led to universal systems that are equivalent in power to Turing machines, it’s just not possible to do any better: any real-world computer or programming language can only ever do as much as a Turing machine can do, and no more. Whether it’s ultimately possible to build a machine that’s more powerful than a Turing machine—that can use exotic laws of physics to perform tasks beyond what we think of as “algorithms”—is not definitively known, but it’s definitely true that we don’t currently know how to do it.

As we saw in Chapter 5, the Turing machine’s simplicity makes it cumbersome to design a rulebook for a particular task. To avoid our investigation of computability being overshadowed by the fiddly details of Turing machine programming, we’ll use Ruby programs as a substitute, just as we did for Euclid’s algorithm.

This sleight of hand is justified by universality: in principle, we can translate any Ruby program into an equivalent Turing machine and vice versa, so a Ruby program is no more or less powerful than a Turing machine, and anything we can discover about the limitations of Ruby’s capabilities should apply equally to Turing machines.

A sensible objection is that Ruby has lots of practical functionality that Turing machines don’t. A Ruby program can access the filesystem, send and receive messages across the network, accept user input, draw graphics on a bitmapped display, and so on, whereas even the most sophisticated set of Turing machine rules can only ever read and write characters on a tape. But that isn’t a fundamental problem, because all of this extra functionality can be simulated with a Turing machine: if necessary, we can designate certain parts of the tape as representing “the filesystem” or “the network” or “the display” or whatever, and treat reading and writing to those tape regions as though it was genuine interaction with the outside world. None of these enhancements changes the underlying computational power of a Turing machine; they just provide higher-level interpretations of its activity on the tape.

In practice, we can sidestep the objection completely by restricting ourselves to simple Ruby programs that avoid any controversial language features. For the rest of this chapter, we’ll stick to writing programs that read a string from standard input, do some computation, and then write a string to standard output when they’re finished; the input string is analogous to the initial contents of a Turing machine’s tape, and the output string is like the final tape contents.

Programs live a double life. As well as being instructions to control a particular system, we can also think of a program as pure data: a tree of expressions, a raw string of characters, or even a single large number. This duality is usually taken for granted by us as programmers, but for general-purpose computers it’s vitally important that programs can be represented as data so that they can be used as input to other programs; it’s the unification of code and data that makes software possible in the first place.

We’ve already seen programs-as-data in the case of the universal Turing machine, which expects another Turing machine’s rulebook to be written on its tape as a sequence of characters. In fancy homoiconic programming languages like Lisp^[66] and XSLT, programs are explicitly written as data structures that the language itself can manipulate: every Lisp program is a nested list called an s-expression, and every XSLT stylesheet is an XML document.

In Ruby, only the interpreter (which, at least in the case of MRI, is not itself written in Ruby) usually gets to see a structured representation of the program, but the code-as-data principle still applies. Consider this simple Ruby program:

puts 'hello world'

To an observer who understands the syntax and semantics of Ruby, this is a program that sends a puts message to the main object with the string 'hello world', which results in the Kernel#puts method printing hello world to standard output. But on a lower level, it’s just a sequence of characters, and because characters are represented as bytes, ultimately that sequence can be viewed as a large number:

>> program = "puts 'hello world'"
=> "puts 'hello world'"
>> bytes_in_binary = program.bytes.map { |byte| byte.to_s(2).rjust(8, '0') }
=> ["01110000", "01110101", "01110100", "01110011", "00100000", "00100111",
    "01101000", "01100101", "01101100", "01101100", "01101111", "00100000",
    "01110111", "01101111", "01110010", "01101100", "01100100", "00100111"]
>> number = bytes_in_binary.join.to_i(2)
=> 9796543849500706521102980495717740021834791

In a sense, puts 'hello world' is Ruby program number 9796543849500706521102980495717740021834791.^[67] Conversely, if someone tells us the number of a Ruby program, we can easily turn it back into the program itself and run it:

>> number = 9796543849500706521102980495717740021834791
=> 9796543849500706521102980495717740021834791
>> bytes_in_binary = number.to_s(2).scan(/.+?(?=.{8}*z)/)
=> ["1110000", "01110101", "01110100", "01110011", "00100000", "00100111",
    "01101000", "01100101", "01101100", "01101100", "01101111", "00100000",
    "01110111", "01101111", "01110010", "01101100", "01100100", "00100111"]
>> program = bytes_in_binary.map { |string| string.to_i(2).chr }.join
=> "puts 'hello world'"
>> eval program
hello world
=> nil

Of course, this scheme of encoding a program as a large number is what makes it possible to to store it on disk, send it over the Internet, and feed it to a Ruby interpreter (which is itself just a large number on disk!) to make a particular computation happen.

We’ve seen that general-purpose computers are universal: we can design a Turing machine that is capable of simulating any other Turing machine, or write a program that can evaluate any other program. Universality is a powerful idea that allows us to use a single adaptable machine for a variety of tasks rather than many specialized devices, but it also has an inconvenient consequence: any system that’s powerful enough to be universal will inevitably allow us to construct computations that loop forever without halting.

So why must every universal system bring nontermination along for the ride? Isn’t there some ingenious way to restrict Turing machines so that they’ll always halt, without compromising their usefulness? How do we know we won’t someday design a programming language that’s just as powerful as Ruby but doesn’t have infinite loops in it? There are all sorts of specific examples of why this can’t be done, but there’s also a more general argument, so let’s go through it.

Ruby is a universal programming language, so it must be possible to write Ruby code that evaluates Ruby code. In principle, we can define a method called #evaluate, which takes the source code of a Ruby program and a string to provide to that program on standard input, and returns the result (i.e., the string sent to standard output) of evaluating that program with that input.

The implementation of #evaluate is far too complicated to be contained within this chapter, but here’s the broadest possible outline of how it would work:

def evaluate(program, input)
  # parse program
  # evaluate program on input while capturing output
  # return output
end

#evaluate is essentially a Ruby interpreter written in Ruby. Although we haven’t given its implementation, it’s certainly possible to write it: first turn program into a sequence of tokens and parse them to build a parse tree (see Parsing with Pushdown Automata), then evaluate that parse tree according to the operational semantics of Ruby (see Operational Semantics). It’s a large and complex job, but it can definitely be done; otherwise, Ruby wouldn’t qualify as universal.

For simplicity, we’ll assume that our imaginary implementation of #evaluate is bug-free and won’t crash while it’s evaluating program—if we’re going to imagine some code, we may as well imagine that it’s perfect. Of course it might return some result that indicates that program raised an exception while it was being evaluated, but that’s not the same as #evaluate itself actually crashing.

require 'stringio'

def evaluate(program, input)
  old_stdin, old_stdout = $stdin, $stdout
  $stdin, $stdout = StringIO.new(input), (output = StringIO.new)

  begin
    eval program
  rescue Exception => e
    output.puts(e)
  ensure
    $stdin, $stdout = old_stdin, old_stdout
  end

  output.string
end

>> evaluate('print $stdin.read.reverse', 'hello world')
=> "dlrow olleh"

The existence of #evaluate allows us to define another method, #evaluate_on_itself, which returns the result of evaluating program with its own source as input:

def evaluate_on_itself(program)
  evaluate(program, program)
end

This might sound like a weird thing to do, but it’s totally legitimate; program is just a string, so we’re perfectly entitled to treat it both as a Ruby program and as input to that program. Code is data, right?

>> evaluate_on_itself('print $stdin.read.reverse')
=> "esrever.daer.nidts$ tnirp"

Since we know we can implement #evaluate and #evaluate_on_itself in Ruby, we must therefore be able to write the complete Ruby program does_it_say_no.rb:

def evaluate(program, input)
  # parse program
  # evaluate program on input while capturing output
  # return output
end

def evaluate_on_itself(program)
  evaluate(program, program)
end

program = $stdin.read

if evaluate_on_itself(program) == 'no'
  print 'yes'
else
  print 'no'
end

This program is a straightforward application of existing code: it defines #evaluate and #evaluate_on_itself, then reads another Ruby program from standard input and passes it to #evaluate_on_itself to see what that program does when run with itself as input. If the resulting output is the string 'no', does_it_say_no.rb outputs 'yes', otherwise, it outputs 'no'. For example:^[69]

$ echo 'print $stdin.read.reverse' | ruby does_it_say_no.rb
no

That’s the result we expected; as we saw above, when we run print $stdin.read.reverse with itself as input, we get the output esrever.daer.nidts$ tnirp, which is not equal to no. What about a program that does output no?

$ echo 'if $stdin.read.include?("no") then print "no" end' | ruby does_it_say_no.rb
yes

Again, just as expected.

So here’s the big question: what happens when we run ruby does_it_say_no.rb < does_it_say_no.rb?^[70] Bear in mind that does_it_say_no.rb is a real program—one that we could write out in full if we had enough time and enthusiasm—so it must do something, but it’s not immediately obvious what that is. Let’s try to work it out by considering all the possibilities and eliminating the ones that don’t make sense.

First, running this particular program with its own source as input can’t possibly produce the output yes. By the program’s own logic, the output yes can only be produced when running does_it_say_no.rb on its own source produces the output no, which contradicts the original premise. So that’s not the answer.

Okay, so maybe it outputs no instead. But again, the structure of the program means that it can only output no if exactly the same computation doesn’t output no—another contradiction.

Is it conceivable that it could output some other string, like maybe, or even the empty string? That would be contradictory too: if evaluate_on_itself(program, program) doesn’t return no then the program prints no, not something different.

So it can’t output yes or no, it can’t output something else, and it can’t crash unless #evaluate contains bugs, which we’re assuming it doesn’t. The only remaining possibility is that it doesn’t produce any output, and that can only happen if the program never finishes: #evaluate must loop forever without returning a result.

This might seem like an unnecessarily complicated way of demonstrating that Ruby lets us write nonhalting programs. After all, while true do end is much a simpler example that does the same thing.

But by thinking about the behavior of does_it_say_no.rb, we’ve shown that nonhalting programs are an inevitable consequence of universality, regardless of the specific features of the system. Our argument doesn’t rely on any particular abilities of Ruby other than its universality, so the same ideas can be applied to Turing machines, or the lambda calculus, or any other universal system. Whenever we’re working with a language that is powerful enough to evaluate itself, we know that it must be possible to use its equivalent of #evaluate to construct a program that never halts, without having to know anything else about the language’s capabilities.

In particular, it’s impossible to remove features (e.g., while loops) from a programming language in a way that prevents us from writing nonhalting programs while keeping the language powerful enough to be universal. If removing a particular feature makes it impossible to write a program that loops forever, it must also have made it impossible to implement #evaluate.

Languages that have been carefully designed to ensure that their programs must always halt are called total programming languages, as opposed to the more conventional partial programming languages whose programs sometimes halt with an answer and sometimes don’t. Total programming languages are still very powerful and capable of expressing many useful computations, but one thing they can’t do is interpret themselves.

The self-referential trick used by does_it_say_no.rb hinges on our ability to construct a program that can read its own source code, but perhaps it seems a bit like cheating to assume that this will always be possible. In our example, the program received its own source as an explicit input, thanks to functionality provided by the surrounding environment (i.e., the shell); if that hadn’t been an option, it could also have read the data directly from disk with File.read(__FILE__), taking advantage of Ruby’s filesystem API and the special __FILE__ constant that always contains the name of the current file.

But we were supposed to be making a general argument that depended only on the universality of Ruby, not on the capabilities of the operating system or the File class. What about compiled languages like Java and C that may not have access to their source at runtime? What about JavaScript programs that get loaded into memory over a network connection, and may not be stored locally on a filesystem at all? What about self-contained universal systems like Turing machines and the lambda calculus, where the notions of “filesystem” and “standard input” don’t exist?

Fortunately, the does_it_say_no.rb argument can withstand this objection, because having a program read its own source from standard input is just a convenient shorthand for something that all universal systems can do, again regardless of their environment or other features. This is a consequence of a fundamental mathematical result called Kleene’s second recursion theorem, which guarantees that any program can be converted into an equivalent one that is able to calculate its own source code. The recursion theorem provides reassurance that our shorthand was justified: we could have replaced the line program = $stdin.read with some code to generate the source of does_it_say_no.rb and assign it to program without having to do any I/O at all.

Let’s see how to do the conversion on a simple Ruby program. Take this one, for example:

x = 1
y = 2
puts x + y

We want to transform it into a program that looks something like this…

program = '…'
x = 1
y = 2
puts x + y

…where program is assigned a string containing the source of the complete program. But what should the value of program be?

A naïve approach is to try to concoct a simple string literal that can be assigned to program, but that quickly gets us into trouble, because the literal would be part of the program’s source code and would therefore have to appear somewhere inside itself. That would require program to begin with the string 'program =' followed by the value of program, which would be the string 'program =' again followed by the value of program, and so on forever:

program = %q{program = %q{program = %q{program = %q{program = %q{program = %q{…}}}}}}
x = 1
y = 2
puts x + y

>> puts %q{Curly brackets look like { and }.}
Curly brackets look like { and }.
=> nil
>> puts %q{An unbalanced curly bracket like } is a problem.}
SyntaxError: syntax error, unexpected tIDENTIFIER, expecting end-of-input

program = 'program = 'program = 'program = \\'…\\''''

The way out of this infinitely deep hole is to take advantage of the fact that a value used by a program doesn’t have to appear literally in its source code; it can also be computed dynamically from other data. This means we can construct the converted program in three parts:

So the structure of the program will be more like this:

data = '…'
program = …
x = 1
y = 2
puts x + y

That sounds plausible as a general strategy, but it’s a bit light on specific details. How do we know what string to actually assign to data in part A, and how do we use it in part B to compute program? Here’s one solution:

This plan still sounds circular—part A produces the source of part B, and part B produces the source of part A—but it narrowly avoids an infinite regress by ensuring that part B just computes the source of part A without having to literally contain it.

We can start making progress by filling in the bits we already know about. We have most of the source of parts B and C already, so we can partially complete the value of data:

data = %q{
program = …
x = 1
y = 2
puts x + y
}
program = …
x = 1
y = 2
puts x + y

We also know that the source of part A is just the string 'data = %q{…}' with the value of data filling the gap between the curly braces, so we can partially complete the value of program too:

data = %q{
program = …
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + …
x = 1
y = 2
puts x + y

Now all that’s missing from program is the source code of parts B and C, which is exactly what data contains, so we can append the value of data to program to finish it off:

data = %q{
program = …
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y

Finally, we can go back and fix up the value of data to reflect what part B actually looks like:

data = %q{
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y

And that’s it! This program does the same thing as the original, but now it has an extra local variable containing its own source code—an admittedly hollow victory, since it doesn’t actually do anything with that variable. So what if we convert a program that expects a local variable called program and does something with it? Take the classic example:

puts program

This is a program that is trying to print its own source code,^[72] but it’s obviously going to fail in that form, because program is an undefined variable. If we run it through the self-referencing transformation we get this result:

data = %q{
program = "data = %q{#{data}}" + data
puts program
}
program = "data = %q{#{data}}" + data
puts program

That’s a bit more interesting. Let’s see what this code does on the console:

>> data = %q{
   program = "data = %q{#{data}}" + data
   puts program
   }
=> "
program = "data = %q{#{data}}" + data
puts program
"
>> program = "data = %q{#{data}}" + data
=> "data = %q{
program = "data = %q{#{data}}" + data
puts program
}
program = "data = %q{#{data}}" + data
puts program
"
>> puts program
data = %q{
program = "data = %q{#{data}}" + data
puts program
}
program = "data = %q{#{data}}" + data
puts program
=> nil

Sure enough, the line puts program really does print out the source code of the whole program.

Hopefully it’s clear that this transformation doesn’t depend on any special properties of the program itself, so it will work for any Ruby program, and the use of $stdin.read or File.read(__FILE__) to read a program’s own source can therefore always be eliminated.^[73] It also doesn’t depend on any special properties of Ruby itself—just the ability to compute new values from old ones, like any other universal system—which implies that any Turing machine can be adapted to refer to its own encoding, any lambda calculus expression can be extended to contain a lambda-calculus representation of its own syntax, and so on.

It’s not obvious why the halting problem should be considered undecidable. After all, it’s easy to come up with individual programs for which the question is answerable. Here’s a program that will definitely halt, regardless of its input string:

input = $stdin.read
puts input.upcase

Conversely, a small addition to the source code produces a program that will clearly never halt:

input = $stdin.read

while true
  # do nothing
end

puts input.upcase

We can certainly write a halting checker to distinguish between only these two cases. Just testing whether the program’s source code contains the string while true is enough:

def halts?(program, input)
  if program.include?('while true')
    false
  else
    true
  end
end

This implementation of #halts? gives the right answers for the two example programs:

>> always = "input = $stdin.read
puts input.upcase"
=> "input = $stdin.read
puts input.upcase"
>> halts?(always, 'hello world')
=> true
>> never = "input = $stdin.read
while true
# do nothing
end
puts input.upcase"
=> "input = $stdin.read
while true
# do nothing
end
puts input.upcase"
>> halts?(never, 'hello world')
=> false

But #halts? is likely to be wrong for other programs. For example, there are programs whose halting behavior depends on the value of their input:

input = $stdin.read

if input.include?('goodbye')
  while true
    # do nothing
  end
else
  puts input.upcase
end

We can always extend our halting checker to cope with specific cases like this, since we know what to look for:

def halts?(program, input)
  if program.include?('while true')
    if program.include?('input.include?('goodbye')')
      if input.include?('goodbye')
        false
      else
        true
      end
    else
      false
    end
  else
    true
  end
end

Now we have a checker that gives the correct answers for all three programs and any possible input strings:

>> halts?(always, 'hello world')
=> true
>> halts?(never, 'hello world')
=> false
>> sometimes = "input = $stdin.read
if input.include?('goodbye')
while true
# do nothing
end
else
puts input.upcase
end"
=> "input = $stdin.read
if input.include?('goodbye')
while true
# do nothing
end
else
puts input.upcase
end"
>> halts?(sometimes, 'hello world')
=> true
>> halts?(sometimes, 'goodbye world')
=> false

We could go on like this indefinitely, adding more checks and more special cases to support an expanding repertoire of example programs, but we’d never get a solution to the full problem of deciding whether any program will halt. A brute-force implementation can be made more and more accurate, but it will always have blind spots; the simple-minded approach of looking for specific patterns of syntax can’t possibly scale to all programs.

To make #halts? work in general, for any possible program and input, seems like it would be difficult. If a program contains any loops at all—whether explicit, like while loops, or implicit, like recursive method calls—then it has the potential to run forever, and sophisticated analysis of the program’s meaning is required if we want to predict anything about how it behaves for a given input. As humans, we can see immediately that this program always halts:

input = $stdin.read
output = ''

n = input.length
until n.zero?
  output = output + '*'
  n = n - 1
end

puts output

But why does it always halt? Certainly not for any straightforward syntactic reason. The explanation is that IO#read always returns a String, and String#length always returns a nonnegative Integer, and repeatedly calling -(1) on a nonnegative Integer always eventually produces an object whose #zero? method returns true. This chain of reasoning is subtle and highly sensitive to small modifications; if the n = n - 1 statement inside the loop is changed to n = n - 2, the program will only halt for even-length inputs. A halting checker that knew all these facts about Ruby and numbers, as well as how to connect facts together to make accurate decisions about this kind of program, would need to be large and complex.

Okay, so our intuition tells us that #halts? would be hard to implement correctly, but that doesn’t necessarily mean that the halting problem is undecidable. There are plenty of difficult problems (e.g., writing #evaluate) that turn out to be solvable given enough effort and ingenuity; if the halting problem is undecidable, that means #halts? is impossible to write, not just extremely difficult.

How do we know that a proper implementation of #halts? can’t possibly exist? If it’s just an engineering problem, why can’t we throw lots of programmers at it and eventually come up with a solution?

def halts?(program, input)
  # parse program
  # analyze program
  # return true if program halts on input, false if not
end

def halts?(program, input)
  # parse program
  # analyze program
  # return true if program halts on input, false if not
end

def halts_on_empty?(program)
  halts?(program, '')
end

program = $stdin.read

if halts_on_empty?(program)
  print 'yes'
else
  print 'no'
end

require 'prime'

def primes_less_than(n)
  Prime.each(n - 1).entries
end

def sum_of_two_primes?(n)
  primes = primes_less_than(n)
  primes.any? { |a| primes.any? { |b| a + b == n } }
end

n = 4

while sum_of_two_primes?(n)
  n = n + 2
end

print n

def halts_on_itself?(program)
  halts?(program, program)
end

def halts?(program, input)
  # parse program
  # analyze program
  # return true if program halts on input, false if not
end

def halts_on_itself?(program)
  halts?(program, program)
end

program = $stdin.read

if halts_on_itself?(program)
  while true
    # do nothing
  end
end