Die Unentscheidbarkeit der Quantifikationstheorie (Theorem von Church)

Wolfgang Stegmüller
Additional contact information
Wolfgang Stegmüller: Universität München

Chapter C in Unvollständigkeit und Unentscheidbarkeit, 1959, pp 44-57 from Springer

Abstract: Zusammenfassung Das Theorem von Church besagt, daß es kein effektives Verfahren gibt, um zu entscheiden, ob eine vorgegebene Formel ein Theorem der Quantifikationstheorie (Prädikatenlogik der ersten Stufe) ist, oder was damit äquivalent ist : ob diese Formel im quantifikatorischen (prädikatenlogischen) Sinn gültig ist35. Da die Quantifikationstheorie zur Logik im engeren Sinne gehört und die Existenz eines effektiven Verfahrens zur Lösung von bestimmten Problemen äquivalent ist mit der Existenz maschineller Lösungsmethoden für jene Probleme, kann man dieses Resultat auch etwas handgreiflicher so ausdrücken: Es ist unmöglich, eine Maschine zu erbauen, die für eine beliebige vorgelegte Aussage auf die Frage, ob diese Aussage rein logisch gültig sei, entweder „ja“ oder „nein“ zur Antwort gibt. Das „unmöglich“ ist hier nicht im Sinn von „faktisch unmöglich“, z. B. „physikalisch unmöglich“, zu verstehen, sondern im Sinn von „logisch unmöglich“ : die Annahme, eine derartige Maschine könnte konstruiert werden, führt zu einem logischen Widerspruch.

Date: 1959
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-7091-3524-2_4

Ordering information: This item can be ordered from
http://www.springer.com/9783709135242

DOI: 10.1007/978-3-7091-3524-2_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().