Tillståndsfråga

Beslutsproblemet ( tyska:  Entscheidungsproblem ) är ett problem i matematikens grunder , formulerat av David Hilbert 1928 : att hitta en algoritm som skulle ta som input en beskrivning av alla lösbarhetsproblem (ett formellt språk och ett matematiskt påstående " " i detta språk) - och, efter ett begränsat antal steg, skulle stanna och ge ett av två svar: "Sant!" eller "False!", beroende på om påståendet " " är sant eller falskt. Svaret kräver ingen motivering, men måste vara sant.

En sådan algoritm skulle till exempel kunna bekräfta Goldbach- hypotesen och Riemann-hypotesen, trots att bevisen (och vederläggningarna) ännu inte är kända. Olösbarheten av upplösningsproblemet (olösbarheten av uppsättningen av sanna aritmetiska formler) för ett aritmetiskt språk som innehåller "likhet", "addition" och "multiplikation" är en konsekvens av den icke-aritmetiska naturen hos denna uppsättning. Nonaritmeticitet är en konsekvens av Tarskis teorem "om oförmågan att uttrycka sanningsbegreppet i ett språk med hjälp av samma språk" [1] .

År 1936 publicerade Alonzo Church och oberoende Alan Turing artiklar där de visade att det inte finns någon algoritm för att bestämma sanningen i påståenden i aritmetik , och därför har det mer allmänna beslutsproblemet heller ingen lösning. Detta resultat är känt som "Church-Turing-satsen" .

Se även

Anteckningar

  1. ↑ V. A. Uspensky , A. L. Semenov Algorithms teori: huvudsakliga upptäckter och tillämpningar, M., Nauka , 1987, 288 s., 2.3 Tillämpningar på matematisk logik: analys av formaliserade logik- och aritmetiska språk

Litteratur