Computability Theory

References

1. Turing AM. On computable numbers, with an application to the Entscheidungsproblem.

Proc Lond Math Soc. 1936–7;s2-42:230–265, 1937;43:544–546.

2. Rogers Jr H. Theory of Recursive Functions and Effective Computability. McGraw-Hill;

1967, MIT Press; 1987.

3. Church A. An unsolvable problem of elementary number theory. Am J Math. 1936;58:

345–363.

4. Shepherdson JC, Sturgis HE. Computability of recursive functions. J Assoc Comput Mach.

1963;10:217–255.

5. Post EL. Recursively enumerable sets of positive integers and their decision problems. Bull

Am Math Soc. 1944;50:284–316.

6. Turing AM. Systems of logic based on ordinals. Proc Lond Math Soc. 1939;s2-45(3):

161–228.

7. Baker T, Gill J, Solovay R. Relativizations of the P = ? N P question.