Entscheidungsproblem

Det Entscheidungsproblem var udfordringen i symbolsk logik for at finde en generel algoritme til at afgøre, om en formel for beregning af den første ordre er et teorem. I 1936, uafhængigt, Alonzo Church og Alan Turing viste både, at det er umuligt at skrive en sådan algoritme. Derfor er det også umuligt at afgøre, om visse specifikke algoritme af aritmetiske sætninger er sande eller falske.

Spørgsmålet går tilbage til Gottfried Leibniz, der i det syttende århundrede, efter lykkedes at opbygge en mekanisk regnemaskine, drømte om at bygge en maskine, der kunne manipulere symboler for at afgøre, om en sætning er en sætning i matematik. Den første ting du vil være nødvendigt, er en klar og præcis formelle sprog, og meget af hans senere arbejde hen imod dette mål. I 1928, David Hilbert og Wilhelm Ackermann foreslog spørgsmålet i sin ovennævnte formulering.

En første ordens logiske formel kaldes universelt gyldige eller logisk gyldig, hvis den følger af aksiomer af calculus af første rang. Den Gödel fuldstændighed teorem, at en logisk formel er universelt gældende i denne forstand, hvis og kun hvis det er sandt, i hvert fortolkning af formlen i en model.

Før du kan besvare dette spørgsmål, var det nødvendigt at formelt at definere begrebet algoritme. Dette blev gjort ved Alonzo Church i 1936 med begrebet "effektiv beregnelighed" baseret på hans lambda calculus og af Alan Turing-maskine baseret på Turing. De to metoder er ækvivalente, i den forstand at det kan løses nøjagtigt de samme problemer med begge metoder.

Entscheidungsproblem negativt svar blev givet af Alonzo Church i 1936 og uafhængigt kort tid derefter af Alan Turing, også i 1936. Kirken bevist, at der ikke er nogen algoritme, der afgør, til to lambda calculus udtryk om de er tilsvarende eller ej. Kirke for denne var baseret på tidligere arbejde af Stephen Kleene. Desuden er det reduceret problemet Turing standse problem for Turing-maskiner. Det anses generelt, at Turing-test har været mere indflydelsesrig end kirken. Begge værker var påvirket af Kurt Gödel tidligere arbejde på hans ufuldstændige sætning, især ved fremgangsmåden i at tildele numre til logiske formler til at reducere logik til aritmetik.

Turing argumentation er som følger: Antag at vi har en generel beslutning algoritme til første-ordens logik. Du kan oversætte spørgsmålet om, hvorvidt en Turing-maskine ender som en første ordens formel, som derefter kunne forelægges beslutningen algoritme. Men Turing havde allerede bevist, at der ikke er nogen generel algoritme, der kan afgøre, om en Turing-maskine stopper.

Det er vigtigt at bemærke, at hvis problemet er begrænset til en bestemt teori af første orden med konstante, konstante prædikater og aksiomer, kan der være en beslutning algoritme til teorien. Eksempler på afgørbare teorier er: aritmetisk Presburger og statiske typesystemer af programmeringssprog.

Imidlertid kan den generelle teori for første ordens naturlige tal kendt som Peano aritmetiske ikke bestemmes med denne type algoritme. Dette følger af argument Turing sammenfattet ovenfor.

Forrige artikel El Campillo de la Jara
Næste artikel Esteban Paredes