We shall try to be precise. There is no single relationship between logic and computation which dominates the others. Here is a list of some of the more important relationships. In my opinion, the importance of this relationship has been exaggerated, because as soon as one goes into what the sentences mean the parallelism disappears. Equivalent classes of problems Certain classes of problems about computations are equivalent to certain classes of problems about formal systems.
E be a program for a stored program digital computer.
Thus, for any Turing machine and initial tape we can find a corresponding formula of the first order predicate calculus such that the Turing machine will eventually stop if and only if the formula is valid. In the case of E if we want strict equivalence the computer must be provided with an infinite memory of some kind. Practically, any present computer has so many states, e.g. , that we cannot reason from finiteness that a computation will terminate or repeat before the solar system comes to an end and one is forced to consider problems concerning actual computers by methods appropriate to machines with an infinite number of states. These results owe much of their importance to the fact that each of the problem classes is unsolvable in the sense that for each class there is no machine which will solve all the problems in the class. These results have been generalized in various ways.