Lupa ongelma

Päätösongelma ( saksaksi:  Entscheidungsproblem ) on David Hilbertin vuonna 1928 muotoilema matematiikan perusteiden ongelma : löytää algoritmi , joka ottaisi syötteenä minkä tahansa ratkaistavuusongelman kuvauksen ( muodollinen kieli ja matemaattinen lausunto " " tämä kieli) - ja rajallisen askelmäärän jälkeen pysähtyi ja antoi jommankumman kahdesta vastauksesta: "Totta!" tai "Epätosi!" riippuen siitä, onko väite " " tosi vai epätosi. Vastaus ei vaadi perusteluja, mutta sen on oltava totta.

Tällainen algoritmi voisi esimerkiksi vahvistaa Goldbach- hypoteesin ja Riemannin hypoteesin, vaikka todisteita (ja kumouksia) ei vielä tunneta. Resoluutioongelman (todellisten aritmeettisten kaavojen joukon ratkaisemattomuus) ratkaisemattomuus aritmeettiselle kielelle, joka sisältää "yhtälön", "lisäyksen" ja "kertojan", on seurausta tämän joukon ei-aritmeettisesta luonteesta. Ei-aritmeettisuus on seurausta Tarskin lauseesta "totuuden käsitteen sanoin kuvaamattomuudesta kielessä saman kielen avulla" [1] .

Vuonna 1936 Alonzo Church ja itsenäisesti Alan Turing julkaisivat artikkeleita, joissa he osoittivat, ettei aritmeettisten väitteiden totuuden määrittämiseen ole algoritmia , ja siksi myös yleisemmällä päätösongelmalla ei ole ratkaisua. Tämä tulos tunnetaan "Church-Turing-lauseena" .

Katso myös

Muistiinpanot

  1. ↑ V. A. Uspensky , A. L. Semenov Algoritmien teoria: tärkeimmät löydöt ja sovellukset, M., Nauka , 1987, 288 s., 2.3 Sovellukset matemaattiseen logiikkaan: formalisoitujen logiikan ja aritmeettisten kielten analyysi

Kirjallisuus