A Précis of Classical Computability Theory

作者: Apostolos Syropoulos

DOI: 10.1007/978-1-4614-8379-3_2

关键词: Rational numberComputability logicAlgebraChurch–Turing thesisComputability theoryComputer scienceSymbol (formal)IntegerTuring machineZero (linguistics)

摘要: Turing machines form the core of computability theory, or recursion theory as it is also known. This chapter introduces basic notions and results readers already familiar with them can safely skip it. The exposition based on standard references [18, 39, 67, 83, 109]. In discussion that follows, symbol ℕ will stand for set positive integer numbers including zero ℚ rational numbers.

参考文章(25)
George S. Boolos, Richard C. Jeffrey, Computability and Logic ,(1974)
Sartaj Sahni, Ellis Horowitz, Fundamentals of Data Structures in Pascal W. H. Freeman & Co.. ,(1984)
P. J. Hilton, L. S. Pontryagin, Foundations of combinatorial topology The Mathematical Gazette. ,vol. 37, pp. 311- ,(1953) , 10.2307/3610096
Gábor Etesi, István Németi, Non-Turing Computations Via Malament-Hogarth Space-Times International Journal of Theoretical Physics. ,vol. 41, pp. 341- 370 ,(2002) , 10.1023/A:1014019225365
Stephen A. Cook, Stȧl O. Aanderaa, ON THE MINIMUM COMPUTATION TIME OF FUNCTIONS Transactions of the American Mathematical Society. ,vol. 142, pp. 291- 314 ,(1969) , 10.1090/S0002-9947-1969-0249212-8
S. C. Kleene, General recursive functions of natural numbers. Mathematische Annalen. ,vol. 112, pp. 727- 742 ,(1936) , 10.1007/BF01565439
Jack Copeland, The Church-Turing Thesis Neuroquantology. ,vol. 2, pp. 101- 115 ,(2007) , 10.14704/NQ.2004.2.2.40