Independent instances for some undecidable problems. (English) Zbl 0517.03022


03F25 Relative consistency and interpretations
03F99 Proof theory and constructive mathematics
03D99 Computability and recursion theory
Full Text: EuDML


[1] 1. M. DAVIS, YU. MATIJASEVIČ and J. ROBINSON, Hilbert’s Tenth Problem. Diophantine Equations : Positive Aspects of a Negative Solution, Proc. Symposia Pure Math., vol. 28, 1976, p. 223-378. Zbl0346.02026 MR432534 · Zbl 0346.02026
[2] 2. S. GREIBACH and J. HOPCROFT, Scattered Context Grammars, J. Comput. Systems Sci., vol. 3, 1969, p. 233-247. Zbl0174.02801 MR246727 · Zbl 0174.02801
[3] 3. J. HARTMANIS and J. HOPCROFT, Independence Results in Computer Science, ACM SIGACT News, vol. 8, 1976, p. 13-24.
[4] 4. Yu. MATIJASEVIC, Enumerable Sets Are Diophantine. Dokl. Akad. Nauk SSSR, vol. 191, 1970, p. 279-282. Zbl0212.33401 MR258744 · Zbl 0212.33401
[5] 5. H. A. MAURER, Simple Matrix Languages with a Leftmost Restriction, Inform. Control, vol., 23, 1973, p. 128-139. Zbl0261.68037 MR388868 · Zbl 0261.68037
[6] 6. J. PARIS and L. HARRINGTON, A Mathematical Incompleteness in Peano Arithmetic, in J. Barwise (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, p. 1133-1142. MR457132
[7] 7. E. POST, A Variant of a Recursively Unsolvable Problem, Bull. AMS, vol. 52, 1946, p. 264-268. Zbl0063.06329 MR15343 · Zbl 0063.06329
[8] 8. H. Jr. ROGERS, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. Zbl0183.01401 MR224462 · Zbl 0183.01401
[9] 9. D. ROSENKRANTZ, Programmed Grammars and Classes of Formal Languages, J. of ACM, vol. 16, 1969, p. 107-131. Zbl0182.02004 MR235940 · Zbl 0182.02004
[10] 10. A. SALOMAA, Formal Languages, Academic Press, New York, London, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.