Top

Published in:

2016 | OriginalPaper | Chapter

11. The Church-Turing Thesis

Author : Bernhard Reus

Published in: Limits of Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The computability results discussed so far used WHILE-programs as choice of “effective procedures”. In this chapter we show that they do not depend on this particular choice of WHILE. Various other (well known) notions of computation are formally introduced. This list includes machine languages like Turing machines, random access memory machines and counter machines, for which a program consists of a sequence of labelled instructions, and jumps are the only control flow mechanisms. We also consider a flow chart language and cellular automata. It is then argued, by means of compilation, that all these languages are equally powerful in the sense that anything that can be programmed in one can be also programmed in any other. This provides evidence for the so-called Church-Turing thesis, that all reasonable formalizations of the intuitive notion of effective computability are equivalent.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Self-referencing Programs

next chapter Measuring Time Usage

Church acknowledges in [5] Kleene’s contributions.

Andrew Hodges (born 1949) is a British mathematician and author of the bestselling biography “Alan Turing—The Enigma” [14] the original 1983 edition of which is the loose (unauthorised) basis for the stage play “Breaking the Code” in 1986 and the movie “The Imitation Game” in 2014.

This will be discussed in Exercise 9.

The language was designed by John Kemeny and Thomas Kurtz in 1964 [8] and was one of the first intended for interactive use.

After all, we have not restricted the length of the tapes for Turing machines.

We have not restricted the size of trees that can be stored in variables of WHILE-programs either.

Born 26 December 1937, John Conway is a British mathematician working in the area of finite groups, number theory, combinatorial game theory and others. He is a Fellow of the Royal Society and professor in Applied and Computational Mathematics at Princeton University.

John von Neumann (December 28, 1903–February 8, 1957) was a Hungarian-born American scientist famous for contributions to various fields, e.g. mathematics, game theory, statistics, and of course computing that all had significant impact. The single-processor, stored-program computer architecture is, for instance, now known as von Neumann machine (or architecture).

Thus, cellular automata are often referred to as “non-standard computation”.

http://www.youtube.com/watch?v=E8kUJL04ELA.

Edward Forrest Moore (November 23, 1925–June 14, 2003) was an American professor of mathematics and computer science, who among other things defined the Moore finite state machine.

This is in analogy with unbounded size of Turing machine tapes.

So nothing can be created out of thin air, i.e. in an entirely “dead” neighbourhood.

This corresponds to the definition of the initial state for a Turing machine where only a finite part is not blank (the input word). This condition could be dropped but then we would have to consider also Turing machine computation with infinite non-empty initial tape or Turing machines with oracles which is not covered in this book.

The concept of “stabilizing computation” is also important for Chemical Reaction Networks in Sect. 22.4.

Other patterns may need a longer interval to repeat their original state.

An excellent and efficient simulator for Life is “Golly” available for all (including mobile) platforms, see [11].

Ralph William Gosper (born 1943) is an American mathematician and programmer famous for his puzzles and among other things his discoveries of moving oscillators in Life.

Stephen Wolfram (born 29 August 1959) is a British physicist, computer scientist and entrepreneur, most famous for being the chief designer of Mathematica published by Wolfram Research whose CEO he is as well.

Issues of how long it takes are covered in the next part of the book about complexity. Other issues, for instance, how easy or convenient it is to program in those languages are not systematically studied here.

Or, seen from the other direction, that the source language can be simulated by the target language.

Without any problem one can generalise this by also encoding the data type of the source language in the data type of the target language. However, this significantly complicates the presentation, so we leave this out. More can be found in [15].

In other words, the compilation is the identity function.

OR, AND, and NOT gates.

Adamatzky, A. (ed.): Game of Life Cellular Automata. Springer, Berlin (2010)

Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays: Volume 2. Academic Press, New York (1982)MATH

Böhm, C., Jacopini, G.: Flow diagrams, turing machines and languages with only two formation rules. Commun. ACM 9(5), 366–371 (1966)CrossRefMATH

Chapman, P.: Life universal computer. Available via DIALOG: http://www.igblan.free-online.co.uk/igblan/ca/index.html. 23 June 2015

Church, A.: An unsolvable problem of elementary number theory. Am. J. Math. 58(2), 345–363 (1936)MathSciNetCrossRefMATH

Cook, M.: Universality in elementary cellular automata. Complex Syst. 15, 1–40 (2004)MathSciNetMATH

Copeland, J.: The Church-Turing Thesis. In: References on Alan Turing. Available via DIALOG. http://www.alanturing.net/turing_archive/pages/Reference%20Articles/The%20Turing-Church%20Thesis.html. 2 June 2015 (2000)

Dartmouth College Computation Center: A manual for BASIC, the elementary algebraic language design for use with the dartmouth time sharing system. 1 Oct 1964. Available via DIALOG: http://www.mirrorservice.org/sites/www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf. 23 June 2015

Gardner, M.: The fantastic combinations of John Conway’s new solitaire game life. Sci. Am. 223, 120–123 (1970)CrossRef

10.

Gardner, M.: On cellular automata, self-reproduction, the garden of eden and the game of life. Sci. Am. 224(2), 112–117 (1971)CrossRef

11.

Golly. An open-source, cross-platform application for exploring Conway’s Game of Life. Available via DIALOG. http://golly.sourceforge.net. 30 Nov 2015

12.

Gomard, C.K., Jones, N.D.: Compiler generation by partial evaluation: a case study. In: Ritter, G. (ed.) Proceedings of the IFIP 11th World Computer Congress, pp. 1139–1144, North-Holland (1989)

13.

Hodges, A.: Alan turing in the stanford encyclopedia of philosophy: introduction. Available via DIALOG. http://www.turing.org.uk/publications/stanford.html. 23 June 2015

14.

Hodges, A.: Alan Turing: The Enigma, Vintage (1992)

15.

Jones, N.D.: Computability and complexity: From a Programming Perspective (Also available online at http://www.diku.dk/neil/Comp2book.html.). MIT Press, Cambridge (1997)

16.

Kari, J.: Cellular automata: a survey. Theor. Comput. Sci. 334, 3–33 (2005)MathSciNetCrossRefMATH

17.

Kemeny, J.G., Kurtz, ‘.T.E.: Back to BASIC: The History, Corruption and Future of the Language. Addison-Wesley Publishing, USA (1985)

18.

Koenig, H., Goucher, A., Greene, D.: Game of Life News. Available via DIALOG: http://pentadecathlon.com/lifeNews/index.php. 19 October 2015

19.

Kun, J.: The cellular automaton method for cave generation. Blog post. Available via DIALOG. http://jeremykun.com/tag/cellular-automata/. 21 July 2015

20.

Mitchell, M.: Computation in cellular automata: A selected review. In Gramss, T., Bornholdt, S., Gross, M., Mitchell, M., Pellizzari, T. (eds.) Nonstandard Computation, pp. 95–140. VCH Verlagsgesellschaft (1998)

21.

Packard, N.H., Wolfram, S.: Two-dimensional cellular automata. J. Stat. Phys. 38(5–6), 901–946 (1985)MathSciNetCrossRefMATH

22.

Rendell, P.: A universal turing machine implemented in conway’s game of life. Available via DIALOG. http://rendell-attic.org/gol/utm/index.htm. 21 July 2015

23.

Rendell, P.: turing universality of the game of life. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 513–539, Springer, Berlin (2002)

24.

Shepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM 10(2), 217–255 (1963)MathSciNetCrossRefMATH

25.

Smith III, A.R.: Simple computation-universal cellular spaces. J. ACM 18(3), 339–353 (1971)MathSciNetCrossRefMATH

26.

Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. series 2 42 (Parts 3 and 4), pp. 230–265 (1936)

27.

Von Neumann, J., Burks, A.W.: Theory of self-reproducing automata. IEEE Trans. Neural Netw. 5(1), 3–14 (1966)

28.

Wainwright, R.T.: Life is universal! Proceedings of the 7th conference on Winter simulation WSC’74, Vol 2, pp. 449–459, ACM (1974)

29.

Wolfram, S.: Computation theory of cellular automata. Commun. Math. Phys. 96(1), 15–57 (1984)MathSciNetCrossRefMATH

Title: The Church-Turing Thesis
Author: Bernhard Reus
Publisher: Springer International Publishing
Book: Limits of Computation
Print ISBN: 978-3-319-27887-2

Electronic ISBN: 978-3-319-27889-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-27889-6_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner