Bruger:C.Thure/Church-Turing-tesen

Church-Turing-tesen er indenfor beregnelighedsteori en hypotese om computeres opførsel. Tesen påstår, at enhver mulig udregning kan udføres af en algoritme på en computer, givet at der er tilstrækkelig meget tid og lagerplads til rådighed. Tesen kan ikke bevises matematisk, og den bliver nogle gange brugt som en definition.

Uformelt siger tesen, at vores opfattelse af "algoritme" kan præciseres, og derved kan algoritmer køres på computere. En computer kan i teorien køre enhver algoritme; hvilket vil sige, at alle almindelige computere er ækvivalente med hensyn til teoretisk beregningskraft (computational power), og det er derfor ikke muligt at konstruere en beregningsenhed, som er mere kraftfuld end den simpleste computer (Turingmaskinen). Det skal nævnes at formuleringen omkring kraft ser bort fra praktiske faktorer som hastighed og hukommelse; den tager højde for alt, som er teoretisk muligt, givet ubegrænset tid og hukommelse.

Tesen blev først fremført af Stephen Kleene i 1943, men opkaldt efter Alonzo Church og Alan Turing, for deres definitioner fra 1936.

Formel fremstilling

Tesen kan fremstilles således:

"Enhver 'funktion som naturligt ville blive betragtet som beregnelig' kan beregnes af en Turingmaskine."

Med baggrund i det svagt formulerede koncept "funktion som naturligt ville blive betragtet som beregnelig", kan tesen ikke formelt blive bevist. Et modbevis vil kun være muligt, hvis man kunne konstruere hypercomputere, hvis resultater "naturligt skulle betragtes som beregnelige".

Ethvert ikke-interaktivt computerprogram kan blive oversat til en Turingmaskine, og enhver Turingmaskine kan oversættes til ethvert Turing-fuldstændigt programmeringssprog, så tesen er ækvivalent med at sige, at ethvert Turing-fuldstændigt programmeringssprog er tilstrækkeligt til at udtrykke enhver algoritme.

Der eksisterer variationer af tesen; f.eks. siger den fysiske Church–Turing-tese:

"Enhver funktion som fysisk kan blive beregnet, kan beregnes af en Turingmaskine."

En anden variation er den stærke Church–Turing-tese (strong Church–Turing thesis), som ikke oprinder fra Church's eller Turings arbejde, men snarere løbende i takt med udviklingen af kompleksitetesteori. Den siger:

"Enhver 'rimelig' beregnelighedsmodel kan effektivt simuleres på en probabilistisk Turingmachine."

Ordet 'effektivt' betyder her op til polynomialtidsreduktioner. Den stærke Church-Turing-tese postulerer da, at alle 'rimelige' beregnelighedsmodeller udtrykker den samme klasse af problemer, som kan beregnes i polynomiel tid. Forudsat formodningen at probabilistisk polynomiel tid (BPP) er lig deterministisk polynomiel tid (P), er order 'probabilistisk' valgfrit i den stærke Church-Turing-tese.

Hvis kvanteberegning var fysisk muligt, ville kvantecomputere modbevise den stærke Church-Turing-tese, da det forudsættes at kvantum polynomiel tid (BQP) er større end BPP. Sagt på en anden måde, der er effektive kvantealgoritmer, som kan udføre opgaver, hvortil der ikke kendes til effektive probabilistiske algoritmer; eksempelvis faktorering af heltal.

Historie

Stephen Kleene fremførte for første gang sin "THESIS I" i en artikel fra 1943 Recursive Predicates and Quantifiers (gentrykt i The Undecidable, s. 255):

"Dette heuristiske faktum [at generelle rekursive funktioner er effektivt beregnelige]...førte Church til at nævne den følgende tese [Kleenes fodnote 22]. Den samme tese er implicit i Turings beskrivelse af beregningsmaskiner [Kleenes fodnote 23].

"THESIS I. Enhver effektivt beregnelig funktion (effektivt afgørbart prædikat) er generelt rekursiv

"I mangel af en præcis matematisk definition af begrebet effektivt beregnelig (effektivt afgørbar), kan vi se denne tese ... som en definition deraf..." (Kleene i Undecidable, s. 274)

Kleenes fodnote 22 referer til Alonzo Churchs artikel, og fodnote 23 refererer til artiklen af Alan Turing. Han fortsætter og noterer at:

"...tesen har karakter af en hypotese -- et synspunkt tydeliggjort af Post og af Church" [hans fodnote 24, The Undecidable, s. 274. Referencerne er til Posts artikel (1936) og til Churchs artikel Formal definitions in the theory of ordinal numbers, Fund. Math. nr. 28 (1936) s. 11-21 (se ref. #2, s. 286, Undecidable)].

In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" Turing tried to capture the notion of algorithm (then called "effective computability"), with the introduction of Turing machines. In that paper he showed that the 'Entscheidungsproblem' could not be solved. A few months earlier Church had proven a similar result in "A Note on the Entscheidungsproblem" but he used the notions of recursive functions and lambda-definable functions to formally describe effective computability. Lambda-definable functions were introduced by Alonzo Church and Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935), and recursive functions were introduced by Kurt Gödel and Jacques Herbrand (Gödel 1934, Herbrand 1932). These two formalisms describe the same set of functions, as was shown in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). After hearing of Church's proposal, Turing was quickly able to show that his Turing machines in fact describe the same set of functions (Turing 1936, 263ff).

Success of the thesis

Since that time, many other formalisms for describing effective computability have been proposed. The three most commonly quoted are the recursive functions, the lambda calculus, and the Turing machine. Stephen Kleene (1952) adds to the list the functions " reckonable in the system S₁" of Kurt Gödel 1936, and Emil Post's (1943, 1946) "canonical [also called normal] systems" (cf Kleene (1952) p. 320). Since Kleene (1952) the various register machines, the various Turing machine-like models such as the Post-Turing machine, combinatory logic, and Markov algorithms have been added to the list. Gurevich adds the pointer machine model of Kolmogorov and Uspensky (1953, 1958): "...they just wanted to ... convince themselves that there is no way to extend the notion of computable function." (Gurevich (1988) p. 2). Gandy (1980) proposed four principles "the formulation [of which] is quite abstract, and can be applied to all kinds of automata and to algebraic systems. It is proved that if a device satisfies the principles then its successive states form a computable sequence." (Gurevich (2000), p. 4).

All these systems have been shown to compute the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. In fact, Gödel (1936) proposed something stronger than this; he observed that there was something "absolute" about the concept of "reckonable in S₁":

"It may also be shown that a function which is computable ['reckonable'] in one of the systems S_i, or even in a system of transfinite type, is already computable [reckonable] in S₁. Thus the concept 'computable' [ 'reckonable' ] is in a certain definite sense 'absolute', while practically all other familiar metamathematical concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined" (translation of Gödel (1936) by Davis in The Undecidable p. 83, differing in the use of the word 'reckonable' in the translation in Kleene (1952) p. 321)

However, the thesis is a definition and not a theorem, and hence cannot be proved true. The physical version could, however, be disproved if a method could be exhibited which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine.

In the early twentieth century, mathematicians often used the informal phrase effectively computable, so it was important to find a good formalization of the concept. Modern mathematicians instead use the well-defined term Turing computable (or computable for short). Since the undefined terminology has faded from use, the question of how to define it is now less important.

The success of the Church–Turing thesis prompted supertheses that extend the thesis, including the strong Church-Turing thesis mentioned earlier.

Philosophical implications

The Church–Turing thesis has been alleged to have some profound implications for the philosophy of mind. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:

1. The universe is equivalent to a Turing machine or is weaker; thus, computing non-recursive functions is physically impossible. This has also been termed the strong Church–Turing thesis (not to be confused with the previously mentioned SCTT) and is a foundation of digital physics.
2. The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
3. The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas (and more famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is no scientific evidence for this proposal.

There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.

References

• Bernstein, E. & Vazirani, U. Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411?1473
• Andreas Blass and Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions, Bulletin of European Association for Theoretical Computer Science 81, 2003. Includes an excellent bibliography of 56 references.
• Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
• Martin Davis editor, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. All the original papers are here including those by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section. Valuable commentary by Davis prefaces most papers.
• Fouché, W., Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
• Robin Gandy, 1980, Church's Thesis and the Principles for Mechanisms, reprinted in H.J. Barwise, H.J. Keisler and K. Kunen, eds., (1980), The Kleene Symposium, North-Holland Publishing Company, pp. 123-148.
• Gödel, K., 1934, On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven Press.
• Gödel, K., 1936, "On The Length of Proofs", reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven Press (pp.82-83), "Translated by the editor from the original article in Ergenbnisse eines mathematishen Kolloquiums, Heft 7 (1936) pp. 23-24." Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll, etc.
• Yuri Gurevich, 1988, On Kolmogorv Machines and Related Issues, Bulletin of European Assoc. for Theor. Comp. Science, Number 35, June 1988, 71-82.
• Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77-111. Includes bibliography of 33 sources.
• Herbrand, J., 1932, "Sur la non-contradiction de l'arithmétique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
• Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
• Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
• Knuth, Donald E.,The Art of Computer Programming, Second Edition, Volume 1/Fundamental Algorithms, Addison-Wesley, 1973.
• Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14. A. A. Markov (1954) Theory of algorithms. Also: [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e. Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
• Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
• Robert Soare, (1995-6), Computability and Recursion, Bulletin of Symbolic Logic 2 (1996), 284--321.
• Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.

Se også

• Beregnelighedsteori
• Afgørbarhed
• Beregnelighedslogik

Eksterne links

• Detaljeret info om Church–Turing-tesen (Stanford Encyclopedia of Philosophy)