Imagine I have written a very useful software tool. It analyses the text of
a program and works out whether it will run to completion and terminate properly
or it will get stuck in an infinite loop.

That isn't very likely. Think about this program:

    #include <iostream>

    using namespace std;

    int main()
    { int N;
      cout << "What number? ";
      cin >> N;

      if (N % 7 == 0)
      { while (true)
        { } }

      else
        cout << "All done\n"; }

Obviously a stand-alone analysis can't reveal the answer. Whether it gets stuck
in a loop or not depends entirely on an unpredictable input.

So I'll make the task easier. My software tool will be given both the program
in question, and the input it will receive when it is run, as two separate files.
To make it easier to get the idea, I'll encapsulate all of this tool in a function:


    string useful(string program_code_file_name,
                  string input_data_file_name)
    { 
      ifstream PROG(program_code_file_name);
      ifstream DATA(input_data_file_name);

      // This function analyses PROG to see what would happen if it ran
      // and received its inputs from DATA. I'll use the notation PROG(DATA)
      // to represent that happening.

      if (PROG(DATA) would eventually terminate)
        return "eventually terminates";
      else
        return "gets stuck and never stops"; }


Now I'll write 2 seemingly poinless fuctions:


1.    void act_out(string behaviour)
      { if (behaviour == "eventually terminates")
          exit(1);

        if (behaviour == "gets stuck and never stops")
        { while (true)
          { } } }


2.    string lie_about(string truth)
      { if (truth == "eventually terminates")
          return "gets stuck and never stops";

        if (truth == "gets stuck and never stops")
          return "eventually terminates"; }


Now we'll consider some combinations.


A.    string duplicate_inputs(string file_name)
      {
        return useful(file_name, file_name);
      }

   This function receives the name of a file, and gives it to useful twice.
   Obviously the file should contain a program if the results are to be
   meaningful, but it doesn't have to. We can't restrict ourselves to
   programs that do something meaningful, we must cover all possibilities.

      duplicate_inputs(PROG) = useful(PROG, PROG)

                    = work out what happens if the program PROG runs, and
                      reads itself is input. Maybe this is a test you would
                      perform on a compiler.

                    = if PROG(PROG) terminates, tell us it terminates;
                      if PROG(PROG) never terminates, tell us that.


B.    lie_about(duplicate_inputs(PROG))

                    = if PROG(PROG) would terminate, tell us that it doesn't;
                      if PROG(PROG) never terminates, tell us it does terminate.


C.    act_out(lie_about(duplicate_inputs(PROG)))

                    = if PROG(PROG) would terminate, go into an infinite loop;
                      if PROG(PROG) never terminates, terminate immediately.

I'll give that combination a name:

D.    EVIL(PROG) = act_out(lie_about(duplicate_inputs(PROG)))

 ***  EVIL(PROG) does the exact opposite (eventual-termination-wise) of what      ***
                 PROG(PROG) does.

                 if the program PROG, given its own source as data, would at some
                 point end, then EVIL(PROG) never ends.
                 if the program PROG, given its own source as data, would never
                 reach an end, then EVIL(PROG) reaches its end.

What happens if the program EVIL is allowed to read itself?

E.    from the part marked *** above,

      EVIL(EVIL) does the exact opposite of what EVIL(EVIL) does.

      It does the exact opposite of what it itself does.

  Spelled out even more, from *** EVIL(X) does the opposite of what X(X) does
  when X is any file containing a program.

  (Even that isn't a requirement. If X is not a program it isn't going to run
  at all. You'd get an immediate error, which means it terminates right away)

  EVIL is a program, so it is a candidate for the input X.

  EVIL(X) does the opposite of X(X), so EVIL(EVIL) does the opposite of EVIL(EVIL).


That is just about the clearest contradiction ever. EVIL(EVIL) can not exist,
but everything done to construct it, except for one thing, is just simple stuff
done all the time.

The one exception is the assumption of the existence of useful().

Nothing that does what useful claims to do can exist. Its existence would lead
to a logical contradiction.

Prediction of the most basic aspect of a program's behaviour (will it ever end)
is impossible.

This is called the Halting Problem.

There are a few things that need to be made clearer:

It is possible to write a program that determines whether another program, reading
a given input, would stop or not. But only if you accept one of three defects:
It will sometimes produce an incorrect answer, or it will sometimge never produce
and answer at all, or both. Anything claiming to that job must have one of those
defects, all of which mean it isn't really doing the claimed job. Trying to do
something but failing doesn't get the job done.

Secondly, many people claim there is an escape. Any digital computer only has
a finite number of bits that determine exactly what it will do next under any
circumstances. It is a huge number, but definitely finite. That means there
are only a finite number of states a computer can be in. It it is is an infinite
loop it must eventually return to a state that it has already been in. So you
could create a device (it would be very expensive, but definitely possible)
that has each of those state bits as its own inputs. It records every combination
of those bits that ever occurs. If a combination is repeated you are in an
infinite loop.

That is because computers are supposed to be deterministic. What they do next
is completely dtermined by their internal state and their inputs. If the same
combination comes up again, the same thing would happen next as did the last time,
so it will keep repeating itself.

The problem with this claim is not that it is totally impractical and unaffordable.
We want an absolute proof of impossibility, showing that it is hard to do is not
enough. The important thing is that if you have N bits of state, then there are
2 to-the-power-of N possible combinations (or states), so 2^N bits would be
required to just record them all. As we saw very recently, two-to-the-power-of N
is the "smallest" operation that is absolutely guaranteed to produce a result that
is bigger than N, even if N is infinite. So we have one of the inevitable defects.
The proposed monitoring device could not monitor itself, that is a case where
it would not work.

In principle, if you are only concerned with detecting loop/halt in an absolutely
trivially tiny computer/program you could create an absolutely ridiculously
enormous device/program that would solve the halting program for it. But that is
not useful, and it is certainly not solving the stated problem. It would only
work for very small cases. You could easily write a similarly useful program.
It just looks at the program it is analysing and if it is exactly precisely this
"int main() { while (true) { } }" it will print "this program will loop forever".
If the program is excatly precisely "int main { exit(0); }" it will print "this
program will eventually halt". For any other inputs it prints "hippopotamusses
are very small". That is a partial solution, it is correct for some inputs.
And you can go on making it more and more sophisticated, working for more and
more cases all the time. But you could never get to a correct program, one
that always produces the correct answer. That is the thing that has been shown
to be impossible.

And although this is not really relevant, consider the sizes involved. For an
exceptionally tiny and almost useless computer with 2K bytes of memory, an 11
bit program counter and an 8 bit accumulator, and maybe three condition flags,
there are a total of 2070 state bits. 2 ^ 2070 is (to seven difts of accuracy)
135,547,300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000 bits of memroy required to monitor that pointlessly
little device.

Because 2^N is always > N even when infinite, nothing can ever be fully aware
of even itself.