Computing degrees of unsolvability. (English) Zbl 0086.01101
References:
| [1] | Kleene, S.: Recursive predicates and quantifiers. Trans. Amer. math. Soc.53, 41-73 (1943). · Zbl 0063.03259 · doi:10.1090/S0002-9947-1943-0007371-8 |
| [2] | Mostowski, A.: On definable sets of positive integers. Fund. math.34, 81-112 (1947). · Zbl 0031.19401 |
| [3] | Post, E.: Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc.50, 284-316 (1944). · Zbl 0063.06328 · doi:10.1090/S0002-9904-1944-08111-1 |
| [4] | Kleene, S., andE. Post: The upper semi-lattice of degrees of recursive unsolvability. Ann. of Math. ser. 2,59, 379-407 (1954). · Zbl 0057.24703 · doi:10.2307/1969708 |
| [5] | Turing, A.: On computable numbers with an application to the Entscheidungsproblem. Proc. London math. Soc., ser. 2,42, 230-265 (1936/37). · Zbl 0016.09701 · doi:10.1112/plms/s2-42.1.230 |
| [6] | Friedberg, R.: Two recursively enumerable sets of incomparable degrees of unsolvability. Proc. Nat. Acad. Sci. (Wash.)43, 236-238 (1957). · Zbl 0080.24302 · doi:10.1073/pnas.43.2.236 |
| [7] | Mostowski, A.: Examples of sets definable by means of two and three quantifiers. Fund. math.42, 259 bis 270 (1955). · Zbl 0066.26201 |
| [8] | Robinson, R.: Arithmetical representation of recursively enumerable sets. J. Symb. Log.21, 162-186 (1956). · Zbl 0073.25204 · doi:10.2307/2268755 |
| [9] | Davis, M.: Computability and Unsolvability. New York: McGraw-Hill 1958. · Zbl 0080.00902 |
| [10] | Rogers, H.: Gödel numberings of partial recursive functions. J. Symb. Log.23, 331-341 (1958). · Zbl 0088.01602 · doi:10.2307/2964292 |
| [11] | Friedberg, R., andH. Rogers: Reducibility and completeness for sets of integers. Z. math. Log.5, H. 2 (1959). · Zbl 0108.00602 |
| [12] | Myhill, J.: Creative sets. Z. math. Log.1, 97-108 (1955). · Zbl 0065.00105 · doi:10.1002/malq.19550010205 |
| [13] | Spector, C.: On degrees of resursive unsolvability. Ann. of Math., ser. 2,64, 581-592 (1956). · Zbl 0074.01302 · doi:10.2307/1969604 |
| [14] | Shapiro, N.: Degrees of computability. Trans. Amer. math. Soc.82, 281-299 (1956). · Zbl 0070.24602 · doi:10.1090/S0002-9947-1956-0085187-3 |
| [15] | Tarski, A.: Sur les ensembles définissables de nombres réels I. Fund. math.17, 210-239 (1931). · JFM 57.0060.02 |
| [16] | Dekker, J.: A theorem on hypersimple sets. Proc. Amer. math. Soc.5, 791-796 (1954). · Zbl 0056.24902 · doi:10.1090/S0002-9939-1954-0063995-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
