Models of Computation

Practical Consequences
For us as computer scientists, we must recognize that there are many things we cannot do.

We cannot write a C program that will determine whether an arbitrary C program will halt on a particular input.
We cannot write a C program that will determine whether two other C programs solve the same problem
A compiler writer cannot produce the smallest assembly language program that solves the same problem as its input (a high-level language program).