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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Languages, Structures, and Theories Kapitel lesen Erstes Kapitel lesen

2024 | OriginalPaper | Buchkapitel

10. Universal Machines and Undecidability

verfasst von : David Marker

Erschienen in: An Invitation to Mathematical Logic

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

Turing’s universal machine is constructed and used to prove the undecidability of the Halting Problem and the undecidability of validity in first-order logic. We include a brief discussion of the Recursion Theorem.

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 Models of Computation
Nächstes Kapitel Computably Enumerable and Arithmetic Sets
Fußnoten
1
In Exercise 14.​25 we give a different pairing function that gives Cantor’s diagonal enumeration of \({\mathbb N}^2\)
 
2
We will also code up some nonsense programs that contain J(\(i,j,n\)), where n is greater than the number of instructions or the program does not end with HALT. By convention, whenever we reach such an instruction we halt.
 
3
Kleene first called this the s-m-n-Theorem,, where \(s,m\), and n referred to various parameters in the statement. Most authors have perpetuated this terminology.
 
4
Here we are thinking informally about machines that take sentences as input. To make this completely precise, we need the machinery of Gödel codes from Chap. 13.
 
5
There is a, perhaps apocryphal, story that Kleene proved the Recursion Theorem while in the dentist’s chair.
 
Metadaten
Titel
Universal Machines and Undecidability
verfasst von
David Marker
Copyright-Jahr
2024
Buch
An Invitation to Mathematical Logic

Print ISBN: 978-3-031-55367-7

Electronic ISBN: 978-3-031-55368-4

Copyright-Jahr: 2024

DOI
https://doi.org/10.1007/978-3-031-55368-4_10

Premium Partner

    Bildnachweise