Spørgsmål om tilladelse

Beslutningsproblemet ( tysk:  Entscheidungsproblem ) er et problem i matematikkens grundlag , formuleret af David Hilbert i 1928 : at finde en algoritme , der som input ville tage en beskrivelse af ethvert løselighedsproblem (et formelt sprog og en matematisk udsagn " " i dette sprog) - og ville efter et begrænset antal trin stoppe op og give et af to svar: "Sandt!" eller "False!", afhængigt af om udsagnet " " er sandt eller falsk. Svaret kræver ikke begrundelse, men skal være sandt.

En sådan algoritme kunne for eksempel bekræfte Goldbach -hypotesen og Riemann-hypotesen, på trods af at beviserne (og gendrivelserne) endnu ikke er kendt. Uløseligheden af ​​opløsningsproblemet (uløseligheden af ​​sættet af sande aritmetiske formler) for et aritmetisk sprog indeholdende "lighed", "addition" og "multiplikation" er en konsekvens af dette sæts ikke-aritmetiske natur. Nonaritmeticitet er en konsekvens af Tarskis teorem "om uudtrykkeligheden af ​​begrebet sandhed i et sprog ved hjælp af det samme sprog" [1] .

I 1936 udgav Alonzo Church og uafhængigt Alan Turing artikler, hvor de viste, at der ikke er nogen algoritme til at bestemme sandheden af ​​udsagn i aritmetik , og derfor har det mere generelle beslutningsproblem heller ingen løsning. Dette resultat er kendt som "Church-Turing-sætningen" .

Se også

Noter

  1. ↑ V. A. Uspensky , A. L. Semenov Algoritmerteori: hovedopdagelser og anvendelser, M., Nauka , 1987, 288 s., 2.3 Anvendelser til matematisk logik: analyse af formaliserede logiske og aritmetiske sprog

Litteratur