Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Limits? What Limits? Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

2. Problems and Effective Procedures

verfasst von : Bernhard Reus

Erschienen in: Limits of Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter provides the basic definition of what we mean by “computable” and what we mean by “problem.” A short historical perspective is given. The term “effective procedure” is introduced that describes a program executable in a finite number of simple steps in a mechanical way. Sets and structures on sets, i.e. relations and functions, together with their basic operations, are defined and some basic reasoning principles reviewed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Limits? What Limits?
Nächstes Kapitel The WHILE-Language
Fußnoten
1
The Association for Computing Machinery (ACM), “the world’s largest educational and scientific computing society, delivers resources that advance computing as a science and a profession” [1]. It was founded in 1947 and has its headquarters in New York.
 
2
And every reader may have their own problems, i.e. their own idea of what a “problem” is.
 
3
The name “algorithm” dates back to the name of the ninth century Persian mathematician Al-Khwarizmi.
 
4
Euclid (ca. 300 BC) was a Greek mathematician often called the “Father of Geometry” who also worked in number theory. He is the inventor of the common divisor algorithm.
 
5
Gottfried Wilhelm von Leibniz (July 1, 1646–November 14, 1716) was a German mathematician and philosopher, credited with the independent invention of differential and integral calculus. He also invented calculating machines.
 
6
Charles Babbage, (December 26, 1791–October 18, 1871) was an English mathematician, philosopher, inventor and mechanical engineer (and a Fellow of the Royal Society). He is also known for originating the concept of a programmable calculating machine. The London Science Museum has constructed two of his machines where they are on display.
 
7
David Hilbert (January 23, 1862–February 14, 1943) was a world-renowned German mathematician.
 
8
Kurt Friedrich Gödel (April 28, 1906–January 14, 1978) was an Austrian (and American) logician, mathematician, and philosopher and is considered one of the most significant logicians in history. He proved many important results, relevant here is the Incompleteness Theorem.
 
9
Alonzo Church (June 14, 1903–August 11, 1995) was an important American mathematician and logician.
 
10
Church’s first version that the computable functions are those definable by \(\lambda \)-terms [3] was initially rejected.
 
11
This type may be a set again.
 
12
The Cartesian product is named in honour of Reneé Descartes (31 March 1596–11 February 1650), a French mathematician and philosopher, who spent most of his life in the Netherlands, and is famous for his saying “I think therefore I am” as well as for the development of (Cartesian) analytical geometry. He was invited to the court of Queen Christina of Sweden in 1649. “In Sweden—where, Descartes said, in winter men’s thoughts freeze like the water—the 22-year-old Christina perversely made the 53-year-old Descartes rise before 5:00 am to give her philosophy lessons, even though she knew of his habit of lying in bed until 11 o’clock in the morning” [9]. Consequently, Descartes caught pneumonia and died.
 
13
The symbol itself is called a “perp”.
 
14
At first glance, it is not obvious whether \(S\times T\times U\) means \(S\times (T\times U)\) or \((S\times T)\times U\). We assume cartesian products to be associative, identifying these two definitions, thus dropping the extra parentheses and writing (s, t, u) for triples, and similarly for n-tuples where \(n>3\).
 
15
Which may possibly be the same type.
 
16
Mathematical objects.
 
17
Boolean values are named after George Boole (2 November 1815–8 December 1864), an English mathematician and logician famous for his work on differential equations and algebraic logic. He is most famous for what is called Boolean algebra. Throughout this book, we will use the term “boolean” to indicate a truth value for which the corresponding algebra operations are available.
 
18
This question is easily confused with the one famously asked in Douglas Adam’s masterpiece: “The Hitchhiker’s Guide to the Galaxy” [2] which actually is called: “Ultimate Question of Life, The Universe, and Everything”. The computer in question, Deep Thought, after a considerable 7.5 million years answered famously: “42”. Alas, nobody understood the question. So Deep Thought suggested to build an even more powerful super-computer to produce the question to the answer. This computer was later revealed to be planet “Earth” which was unfortunately destroyed 5 min before completion of the calculations.
 
Literatur
1.
2.
Adams, D.: The Hitchhiker’s Guide to the Galaxy. Pan Books (1979)
3.
4.
5.
Goldin, D., Wegner, P.: The church-turing thesis: breaking the myth. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) New Computational Paradigms. Lecture Notes in Computer Science, vol. 3526, pp. 152–168. Springer, Heidelberg (2005)
6.
Hilbert, D., Ackermann, W.: Grundzüge der theoretischen Logik. Springer, Berlin (1928). (Principles of Mathematical Logic.)
7.
8.
Makinson, D.: Sets, Logic and Maths for Computing, 2nd edn. Springer, UTiCS Series (2012)
9.
10.
Soare, R.I.: The history and concept of computability. In: Griffor, E.R. (ed.) Handbook of Computability Theory, pp. 3–36. North-Holland (1999)
11.
12.
Metadaten
Titel
Problems and Effective Procedures
verfasst von
Bernhard Reus
Copyright-Jahr
2016
Buch
Limits of Computation

Print ISBN: 978-3-319-27887-2

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

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-27889-6_2