Structure of Decidable Locally Finite Varieties - Couverture souple
Livre 9 sur 170: Progress in Mathematics
Synopsis
Eine mathematisch genaue Definition des intuitiven Begriffs des "Algorithmus" war in Kurt Godels Papier über formal unentscheidbare Propo-Sitionen der Arithmetik implizit. In den 1930er Jahren entwickelte sich Godels Idee in der Arbeit von Mathematien wie Alonzo Church, Stephen Kleene, Barkley Rosser und Alfred Tarski zum Konzept einer rekursiven Funktion. Church pro stellte die heute allgemein akzeptierte These auf, dass ein effektiver Algorithmus dasselbe ist wie eine Prozedur, deren Ausgabe eine rekursive Funktion der Eingabe ist (geeignet als Ganzzahl codiert). Mit diesen Konzepten wurde es möglich zu beweisen, dass viele bekannte Theorien unentscheidbar (oder nicht-rekursiv) sind, d.h. dass es keinen effektiven Algorithmus (rekursive Funktion) gibt, der es ermöglichen würde, zu bestimmen, welche Sätze zur Theorie gehören. Es war von Anfang an klar, dass jede Theorie mit einem ausreichend reichen mathematischen Inhalt unentscheidbar sein muss. Andererseits sind einige Theorien mit einem substanziellen Inhalt entscheidbar. Beispiele für solche dezidabLe Theorien sind die Theorie der Booleschen Algebren (Tarski [1949]), die Theorie der Abelschen Gruppen (Szmiele~ [1955]) und die Theorien der Elementararithmetik und Geometrie (Tarski [1951]", aber Tarski entdeckte diese Ergebnisse um 1930). Die Beendigung präziser Trennlinien zwischen den Klassen der entscheidbaren und unentscheidbaren Theorien wurde zu einem wichtigen Forschungsziel auf diesem Gebiet. Algebra meinen wir einfach jede Struktur (A, h(i E I)}, bestehend aus Durch eine nicht-leere Menge A und ein System von finitären Operationen Ii über A.
Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.
