Engedély kérdése

A döntési probléma ( németül  Entscheidungsproblem ) a matematika alapjaiban felmerülő probléma, amelyet David Hilbert fogalmazott meg 1928- ban : olyan algoritmust találni , amely bemenetként bármilyen megoldhatósági probléma leírását veszi (egy formális nyelv és egy matematikai kijelentés " " ez a nyelv) - és véges számú lépés után megáll, és a két válasz egyikét adja: "Igaz!" vagy "Hamis!", attól függően, hogy a " " állítás igaz vagy hamis. A válasz nem igényel indoklást, de igaznak kell lennie.

Egy ilyen algoritmus megerősítheti például a Goldbach -hipotézist és a Riemann-hipotézist, annak ellenére, hogy a bizonyítások (és a cáfolatok) még nem ismertek. Az "egyenlőséget", "összeadást" és "szorzást" tartalmazó aritmetikai nyelv esetében a feloldási probléma (az igaz aritmetikai képletek halmazának megoldhatatlansága) nem aritmetikai jellegének a következménye. A nonaritmeticitás Tarski „az igazság fogalmának ugyanazon nyelven keresztüli kifejezhetetlenségéről” szóló tételének következménye [1] .

1936- ban Alonzo Church és egymástól függetlenül Alan Turing publikált tanulmányokat, amelyekben kimutatták, hogy nincs algoritmus az állítások igazságának meghatározására az aritmetikában , ezért az általánosabb döntési problémának sincs megoldása. Ezt az eredményt "Church-Turing-tételnek" nevezik .

Lásd még

• Godel befejezetlenségi tétele

Jegyzetek

1. ↑ V. A. Uspensky , A. L. Semenov Algoritmusok elmélete: fő felfedezések és alkalmazások, M., Nauka , 1987, 288 pp., 2.3 Alkalmazások a matematikai logikára: a logikai és aritmetikai formalizált nyelvek elemzése

Irodalom

• Alonzo templom. Az elemi számelmélet megoldhatatlan problémája  // American Journal of Mathematics. - 1936. - 1. évf. 58. - P. 345-363. - doi : 10.2307/2371045 .
• Alonzo templom. Megjegyzés az Entscheidungsproblemhez // Journal of Symbolic Logic. - 1936. - 1. évf. 1. - P. 40-41.
• Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem  (angol) // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - P. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230
• Turing A. M. A kiszámítható számokról, az Entscheidungsproblem alkalmazásával. A Correction  (angol) // Proceedings of the London Mathematical Society - London Mathematical Society , 1938. - Vol. s2-43, Iss. 6. - P. 544-546. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-43.6.544
• Edelman S.L. Matematikai logika. - M . : Felsőiskola, 1975. - 176 p.