Lyhyt MathCheck-ohje (uuteen välilehteen)
Tietojenkäsittelytiede alkoi Alan Turingin julkaisusta vuonna 1936. Siinä hän esitti matemaattisen mallin tietokoneille ja niiden ohjelmille sekä todisti, että on olemassa tehtäviä, jotka näyttävät tietokoneille sopivilta, mutta joita ei kuitenkaan voi ratkaista yleispätevästi tietokoneilla.
Koska tuolloin ei ollut ohjelmointikieliä, Turing joutui selittämään monet asiat vaikeasti. Ratkeamattomien tehtävien olemassaolo on nykyisin todistettavissa hyvin yksinkertaisesti vetoamalla ohjelmoinnista tuttuihin asioihin. Tuskin mikään muu matemaattisten tieteiden suurista saavutuksista on yhtä helppo ymmärtää läpikotaisin yhtä vähillä taustatiedoilla!
Tässä tehtävässä todistetaan, että kysymys pysähtyykö annettu ohjelma annetulla syötteellä on ratkeamaton. Sitten johdetaan joitakin jatkotuloksia, jotka kertovat, että ratkeamattomuus on hyvin yleinen ilmiö. Koodinpätkien toisiinsa liittämisen helpottamiseksi koko ajan puhutaan aliohjelmista, mutta tulokset pätevät myös ohjelmille, koska aliohjelmasta on helppo tehdä ohjelma lisäämällä pääohjelma joka kutsuu sitä.
Ennen kuin voimme käydä käsiksi pääasiaan, meidän täytyy ottaa käyttöön muutamia merkintöjä. Oikeilla ohjelmointikielillä syntyisi pitkiä ilmauksia, joissa pääasia hukkuu sen kannalta merkityksettömien yksityiskohtien alle. Siksi käytämme matematiikasta ja tietojenkäsittelytieteestä peräisin olevia merkintöjä.
Kuten matematiikassa ja tietojenkäsittelytieteessä on tapana, pienet kreikkalaiset kirjaimet σ, ρ, π ja niin edelleen ovat muuttujia, joiden tyyppi on merkkijono. Kaikkien merkkijonojen joukkoa merkitään Σ*. Niinpä σ ∈ Σ* tarkoittaa, että σ:n tyyppi on merkkijono. Myös merkkijonovakioiden kuten ”talo” tyyppi on merkkijono. Siksi ”talo” ∈ Σ*. Merkkijonovakion alku ja loppu osoitetaan ”:lla, jotta siinä voisi olla muun muassa välilyöntejä ja silti erottuisi, mistä se alkaa ja mihin se loppuu. Merkkijonon σ pituutta merkitään |σ|. Esimerkiksi |”talo”| = 4, |”merkkijono”| = 10 ja |””| = 0.
Muuttujat i, j, …, n sisältävät luonnollisia lukuja 0, 1, 2, … eli niiden tyyppi on luonnollinen luku. Luonnollisten lukujen joukkoa merkitään ℕ:llä. Esimerkiksi 0 ∈ ℕ ja m ∈ ℕ. Käytämme myös tyyppiä totuusarvo eli 𝔹. Totuusarvovakioita on kaksi: F eli epätosi ja T eli tosi. Siis 𝔹 = {F, T}. Muuttujien nimissä voi olla alaindeksejä tyyliin σ1 tai ni. Kun tarvitsemme helposti muistettavaa nimeä, kirjoitamme esimerkiksi laskuri ja kerromme tyypin erikseen.
Mikä on seuraavien olentojen tyyppi sanoina ilmaistuna, ja mikä on tyypin joukkosymboli? 253luonnollinen luku ℕ ”253”merkkijono Σ* |”talo”|luonnollinen luku ℕ Ftotuusarvo 𝔹 ρnmerkkijono Σ* m + 1luonnollinen luku ℕ n > 2totuusarvo 𝔹 ”n > 2”merkkijono Σ* Mallivastaus tulee näkyviin siirtämällä kursori ruskean alueen päälle.
Oletamme, että on valittu jokin yleiskäyttöinen ohjelmointikieli. Kaikki jatkossa mainittavat aliohjelmat on kirjoitettu sillä. Aliohjelmatkin ovat merkkijonoja. Jos π on aliohjelma, jonka syöte on yksi merkkijono, niin merkinnällä π(σ) tarkoitamme tilanteesta riippuen π:n suoritusta syötteellä σ tai tämän suorituksen tulosta. Vastaavasti π(σ, ρ, i):n syöte koostuu kahdesta merkkijonosta ja yhdestä luonnollisesta luvusta.
Jos aliohjelman suoritus pysähtyy, niin sen tulos on luku, merkkijono tai totuusarvo. Jos aliohjelman suoritus ei pysähdy, niin sanomme, että tulos on ⊥. Niinpä π(σ) = ⊥ tarkoittaa, että π(σ) ei pysähdy. Symboli ⊥ ei kuulu aliohjelman tuloksen tyyppiin vaan ilmaisee, että aliohjelma jää ikuiseen silmukkaan eikä siksi palauta mitään.
Seuraavan aliohjelman nimi tulee sanasta ”vähennyssilmukka”. Alleviivattu rivi ilmoittaa aliohjelman nimen, parametrit tyyppeineen ja tuloksen tyypin.
väsi(n ∈ ℕ, m ∈ ℕ) ∈ ℕ
while n ≥ m do
n := n − m
return n
Aliohjelman parametrit välitetään mekanismilla, jota kutsutaan arvon välitykseksi. Olennaista siinä on, että aliohjelman parametrinsa arvolle tekemät muutokset eivät näy kutsujalle. Vaikka aliohjelman parametrilla olisi sama nimi kuin kutsujan muuttujalla, ne ovat silti erilliset muuttujat. Esimerkiksi jos n = 5 ja kutsutaan väsi(n, 2), niin kutsun jälkeenkin kutsujan n on 5 vaikka väsi:n n muuttui ykköseksi.
Aliohjelmia voi käyttää toistensa aliohjelmina. Niinpä esimerkiksi π( π1(σ), π2(ρ, i) ) tarkoittaa aliohjelmaa, joka suorittaa π1:n syötteellä σ ja π2:n syötteellä, jonka osat ovat ρ ja i. Sitten se käyttää näin saatuja tuloksia π:n syötteenä ja suorittaa π:n.
Oletamme seuraavissa kysymyksissä, että π(3) = 5, π(4) = ⊥, ja että κ(n, m) laskee kertolaskun n ⋅ π(m) ja palauttaa tuloksen.
μ(n ∈ ℕ, m ∈ ℕ) ∈ ℕ
if n = 0 then
return 0
else
return κ(n, m)
Määritelmä Pysähtymistesteri on mikä tahansa aliohjelma pt, jolla on seuraavat ominaisuudet. Sen syöte on kaksi merkkijonoa ja tulos on totuusarvo. Jos π:n sisältö on aliohjelma, jonka syöte on yksi merkkijono ja joka pysähtyy syötteellä σ, niin pt(π, σ) = T. Muussa tapauksessa pt(π, σ) = F.
Mikä on kutsun pt(π, σ) tulos, jos π:n sisältö ei ole aliohjelma vaan jokin muu merkkijono? vastausF
Mikä on kutsun pt(väsi, ”5, 2”) tulos? vastausF, koska väsi:n syöte ei ole yksi merkkijono vaan kaksi luonnollista lukua.
Olkoon seuraavissa kysymyksissä π(σ) aliohjelma, joka tunnistaa σ:n alusta kaksi pilkulla toisistaan erotettua luonnollista lukua n ja m, ja sitten kutsuu väsi(n, m) ja palauttaa sen tuloksen omana tuloksenaan.
Aliohjelma pt ei voi toimia siten, että se ajaa π(σ):n ja katsoo pysähtyykö se, sillä niin toimiva pt(π, σ) epäonnistuisi tällä tavallaJos π(σ) ei pysähdy, niin sellainen pt(π, σ) jää ikuisesti odottamaan π(σ):n vastausta eikä niin ollen itsekään pysähdy.. Siis pätisi pt(π, σ) = ⊥, vaikka pitäisi olla pt(π, σ) = F. Jatkossa käsite ”testeri” sisältää aina vaatimuksen, että se pysähtyy kaikilla syötteillä. Jos halutaan luopua tästä vaatimuksesta, niin käytetään termiä ”osittainen testeri”.
Todistamme, että pt ei voi toimia millään muullakaan tavalla; todistamme siis, että pysähtymistestereitä ei ole olemassa. Teemme sen ottamalla tarkasteluun minkä tahansa aliohjelman χ, jolla on sama syötteen ja tuloksen tyyppi kuin pt:llä, ja todistamalla, että ainakin yhdellä syötteellä se ei vastaa lainkaan tai vastaa eri tavalla kuin pysähtymistesteri vastaisi. Koska se ei vastaa aina kuten pysähtymistesteri vastaisi, se ei ole pysähtymistesteri. Päättely toteutetaan siten, että se pätee jokaiselle aliohjelmalle, jolla on sama syötteen ja tuloksen tyyppi kuin pysähtymistesterillä. Siksi mikään aliohjelma ei voi olla pysähtymistesteri.
Olkoon siis χ mikä tahansa aliohjelma, joka ottaa syötteekseen kaksi merkkijonoa, ja palauttaa totuusarvon tai ei pysähdy. Osoitamme kohta, että χ(π, σ) vastaa eri tavalla kuin pysähtymistesteri vastaisi tai ei vastaa lainkaan, jos π = σ = ξχ, missä ξχ on seuraava aliohjelma:
ξχ(σ ∈ Σ*) ∈ ℕ
n := 0
if χ(σ, σ) then
while n ≥ 0 do
n := n − 0
return n
Tässä χ on alaindeksinä korostamassa sitä, että jokaisella χ on ikioma ξχ (sen sijaan että olisi yksi ξ jota käyttäisimme kaikille χ). Emme kirjoita ξ(χ, σ), koska se tarkoittaisi että χ on osa ξ:n syötettä. Sitä se ei ole, vaan χ on osa aliohjelman ξχ koodia.
Kahdessa jälkimmäisessä tapauksessa ξχ(ξχ) itse huolehtii, että χ(ξχ, ξχ):n vastaus on eri kuin mitä pysähtymistesteri vastaisi, pyytämällä χ(ξχ, ξχ):n vastauksen ja sitten tekemällä päinvastoin.
Olemme todistaneet seuraavan lauseen:
Lause 1 Pysähtymistesteriä ei ole olemassa. Toisin sanoen, ei voida kirjoittaa aliohjelmaa, joka ottaa syötteekseen merkkijonot π ja σ ja vastaa aina oikein kysymykseen ”onko π aliohjelma, joka ottaa syötteekseen yhden merkkijonon, ja pysähtyy jos tämä merkkijono on σ”.
Kyllä/ei-kysymystä sanotaan ratkeamattomaksi, jos ja vain jos ei ole olemassa aliohjelmaa, joka pysähtyy kaikilla syötteillä ja palauttaa T tai F sen mukaan onko kysymyksen vastaus annetulla syötteellä ”kyllä” vai ”ei”. Olemme juuri todistaneet, että seuraava kysymys, joka saa syötteekseen merkkijonot π ja σ, on ratkeamaton: ”esittääkö π aliohjelmaa, jonka syöte on yksi merkkijono, ja joka pysähtyy jos se ajetaan syötteenään σ”.
Tyhjän syötteen pysähtymistesteri on muuten samanlainen kuin pysähtymistesteri, mutta se ottaa syötteekseen vain yhden merkkijonon ja tutkii, esittääkö se aliohjelmaa, jonka syöte on yksi merkkijono ja joka pysähtyy jos tämä merkkijono on tyhjä.
Määritelmä Tyhjän syötteen pysähtymistesteri on mikä tahansa aliohjelma tspt, jolla on seuraavat ominaisuudet. Jos π:n sisältö on aliohjelma, jonka syöte on yksi merkkijono ja joka pysähtyy syötteellä ””, niin tspt(π) = T. Muussa tapauksessa tspt(π) = F.
Tarvitsemme jatkossa useasti ilmausta ”aliohjelma, jonka syöte on yksi merkkijono”. Siksi annamme sille lyhenteen ajsoym.
Tyhjän syötteen pysähtymistestereitäkään ei ole olemassa. Todistamme tämän olettamalla, että sellainen on olemassa, ja rakentamalla sen avulla pysähtymistesterin. Näin päädytään ristiriitaan Lauseen 1 kanssa, joten tyhjän syötteen pysähtymistestereitä ei ole olemassa.
Tarvitsemme keinon sisällyttää merkkijonovakioon lainausmerkki. Käytämme samaa ratkaisua kuin monissa ohjelmointikielissä: pelkkä ” tarkoittaa merkkijonon loppua, mutta \” tarkoittaa merkkijonon sisällä olevaa lainausmerkkiä. Seuraava C++-esimerkki havainnollistaa tätä.
lause tulostaa std::cout << "Se on " << n << "!"; Se on 3! std::cout << "Se on \" << n << \"!"; Se on " << n << "!
Kuinka monta ja minkätyyppisiä parametreja std::cout saa ylärivissäkolme: merkkijono, luku, merkkijono? Entä alarivissäyhden: merkkijono?
Merkkijonojen laittaminen peräkkäin esitetään matematiikassa
laittamalla niitä edustavat symbolit peräkkäin.
Jos esimerkiksi σ = ”pii” ja ρ = ”rakka”, niin σρ = ”piirakka”.
(Kittilän Levillä on sen niminen tie.)
Ilmaus ”σ := \””ρ”\”” rakentaa merkkijonon laittamalla peräkkäin kolme osaa,
joista ensimmäinen koostuu näistä merkeistäσ
välilyönti
:
=
välilyönti
”;
keskimmäinen on tämäρ:n
sisältö; ja viimeinen on tämä”.
Jos ρ = ”hauva”, niin ”σ := \””ρ”\”” = tämä”σ := \”hauva\””.
Olkoon koodin_alkuun(α, β) aliohjelma, joka tulkitsee merkkijonon α sisältöä aliohjelmaksi kunnes löytää kohdan jossa parametrien ja tuloksen tyypin määrittely loppuu ja suoritettava koodi alkaa, lisää siihen merkkijonon β omalle rivilleen, ja palauttaa tuloksen. Kaikilla syötteillä pysähtyvä oikein toimiva koodin_alkuun voidaan toteuttaa, sillä lisäyksen paikka löytyy kääntäjätekniikalla ja muu on helppoa. Esimerkiksi jos π on
π(σ ∈ Σ*) ∈ ℕ
k := |σ|
return 2k + 1
niin koodin_alkuun(π, ”σ := \”hauva\””) on
π(σ ∈ Σ*) ∈ ℕ
σ := ”hauva”
k := |σ|
return 2k + 1
Jos tspt olisi olemassa, niin voitaisiin kirjoittaa aliohjelma γ(π, ρ), joka ensin lisää π:n suoritettavan osan alkuun sijoituslauseen, jossa π:n syöte korvataan ρ:sta saadulla merkkijonovakiolla. Sitten se testaa näin muutetun π:n tspt:llä ja palauttaa testin tuloksen. Jotta alkuperäinen ja muutettu π eivät menisi sekaisin, merkitsemme alkuperäistä π:llä ja muutettua πρ:lla.
γ(π ∈ Σ*, ρ ∈ Σ*) ∈ 𝔹Se käyttäytyy seuraavasti:
πρ := koodin_alkuun(π, ”σ := \””ρ”\””)
return tspt(πρ)
Siis γ(π, ρ) tuottaa aina saman tuloksen kuin pysähtymistesteri tuottaisi, joten γ(π, ρ) on pysähtymistesteri. Olemme osoittaneet, että jos tyhjän syötteen pysähtymistesteri olisi olemassa, niin sen avulla voitaisiin toteuttaa pysähtymistesteri. Lauseen 1 mukaan pysähtymistesteriä ei ole olemassa, joten saamme lauseen 2:
Lause 2 Tyhjän syötteen pysähtymistesteriä ei ole olemassa.
Määritelmä Osittainen tyhjän syötteen pysähtymistesteri on mikä tahansa aliohjelma otspt, jolla on seuraavat ominaisuudet. Se ottaa syötteekseen yhden merkkijonon ja palauttaa F tai T tai jää ikuiseen silmukkaan. Jos otspt(π) = T, niin π:n sisältö on ajsoym joka pysähtyy syötteellä ””. Jos otspt(π) = F, niin π:n sisältö ei ole ajsoym tai sei ei pysähdy syötteellä ””.
Osittaisia tyhjän syötteen pysähtymistestereitä on olemassa. Niistä yksinkertaisin (ja hyödyttömin) on ajsoym, jonka tuloksen tyyppi on totuusarvo ja joka jää kaikilla syötteillä ikuiseen silmukkaan.
surkea_otspt(σ ∈ Σ*) ∈ 𝔹
while T do
n := 0
return F
Hieman parempi aloittaa tutkimalla, esittääkö sen syöte π ajsoymia (tämä osataan tehdä ja siihen tarvittavia menetelmiä käsitellään muun muassa kääntäjätekniikan kursseilla). Jos ei esitä, se palauttaa F. Jos esittää, se ajaa π(””) ja sen valmistuttua palauttaa T. Mitä tämä osittainen tyhjän syötteen pysähtymistesteri tekee, jos π on ajsoym, joka ei pysähdy tyhjällä syötteellä? vastausJää ikuiseen silmukkaan.
Vielä parempi osittainen tyhjän syötteen pysähtymistesteri saadaan lisäämällä π:n tutkimisen ja π(””):n ajamisen väliin testejä, joissa tunnistetaan tyhjällä syötteellä ikuiseen silmukkaan jääviä aliohjelmia ja palautetaan niille F. Seuraava aliohjelma havainnollistaa tätä ajatusta.
parempi_otspt(π ∈ Σ*) ∈ 𝔹
if π:n sisältö ei ole ajsoym then
return F
if π = surkea_otspt then
return F
if π = jokin_toinen_pysähtymätön then
return F
π(””)
return T
Jos jollakin osittaisella tyhjän syötteen pysähtymistesterillä olisi vain 7 syötettä, joilla se jää ikuiseen silmukkaan, niin siihen voitaisiin lisätä testit, jotka tunnistavat ne ja palauttavat niille F. Näin saataisiin osittainen tyhjän syötteen pysähtymistesteri, joka pysähtyy kaikilla syötteillä. Tämä ei kuitenkaan voi onnistua, koska …Sellainen osittainen tyhjän syötteen pysähtymistesteri olisi tyhjän syötteen pysähtymistesteri, mutta tyhjän syötteen pysähtymistesteriä ei ole olemassa.
Tämä pätee tietenkin, olipa 7:n paikalla mikä tahansa luonnollinen luku. Olemme todistaneet seuraavan.
Lause 3 Jokaisella osittaisella tyhjän syötteen pysähtymistesterillä on äärettömän monta syötettä, joilla se jää ikuiseen silmukkaan.
Päättelyissämme on tyypillisesti ollut kolme haaraa: tutkittava merkkijono ei ole ajsoym, se on ajsoym joka pysähtyy tutkittavalla syötteellä, tai se on ajsoym joka ei pysähdy tutkittavalla syötteellä. Tähän mennessä on toivottavasti tullut selväksi, että asian ydin on kahdessa jälkimmäisessä. Jatkossa unohdamme tapauksen ”ei ole ajsoym” luottaen siihen, että se voidaan hoitaa kuten edellä.
Tämän alaluvun ajan oletamme, että merkistö sisältää ainakin numeromerkit 0, 1, …, 9 ja isot kirjaimet A, B, …, Z.
Tarkastelemme kysymystä ”onko π ajsoym, joka pysähtyy ainakin niillä syötteillä, joissa esiintyy kirjain A?” Jos sille olisi olemassa testeri testaa_A, niin voitaisiin kirjoittaa aliohjelma χ(π, σ), joka ensin sijoittaa muuttujaan ξ merkkijonovakion joka sisältää alla olevan aliohjelman ξπ, σ, ja sitten testaa sen.
ξπ, σ(ρ ∈ Σ*) ∈ 𝔹
π(σ)
return T
Siis näin:
χ(π, σ)
ξ := ξπ, σ
return testaa_A(ξ)
Voiko χ(π, σ) jäädä ikuiseen silmukkaan? vastausEi voi. Aliohjelman ξπ, σ kirjoittaminen on yksinkertaista merkkijonojen käsittelyä, joka saadaan onnistumaan aina. Kutsu testaa_A(ξ) ei koskaan jää ikuiseen silmukkaan, koska aliohjelmaa ei sanota testeriksi, jollei se pysähdy kaikilla syötteillä. Testerin kaltaista aliohjelmaa, jolla on lupa jäädä joillakin syötteillä ikuiseen silmukkaan, kutsutaan tällä termilläosittainen testeri.
Jos π pysähtyy syötteellä σ, niin ξπ, σ(”Sano AA!”) tekee näinPysähtyy ja palauttaa T. ja ξπ, σ(”Enkä.”) tekee näinPysähtyy ja palauttaa T.. Mitä ξπ, σ tekee muilla syötteillä? vastausPysähtyy ja palauttaa T. Sen käyttäytyminen ei riipu syötteestä. Merkkijonot π ja σ eivät ole osa sen syötettä, vaan ne on kirjoitettu ξπ, σ:n koodiin sellaisinaan. ξπ, σ:n syöte on ρ. Kutsu χ(π, σ) palauttaa tämänT, koska …ξπ, σ pysähtyy ainakin niillä syötteillä, joissa esiintyy kirjain A, koska se pysähtyy aivan kaikilla syötteillä..
Jos π ei pysähdy syötteellä σ, niin ξπ, σ(”Sano AA!”) tekee näinEi pysähdy. ja ξπ, σ(”Enkä.”) tekee näinEi pysähdy.. Mitä ξπ, σ tekee muilla syötteillä? vastausEi pysähdy. Kuten edellä, sen käyttäytyminen ei riipu syötteestä. Kutsu χ(π, σ) palauttaa tämänF, koska …ξπ, σ ei pysähdy edes niillä syötteillä, joissa esiintyy kirjain A, koska se ei pysähdy millään syötteillä..
Siis χ(π, σ) pysähtyy aina ja vastaa kuten pysähtymistesteri vastaisi. Se siis olisi pysähtymistesteri! Näin ei voi olla, koska …Lauseen 1 mukaan pysähtymistesteriä ei ole olemassa. Niinpä aliohjelmaa testaa_A ei ole olemassa, joten kysymys ”onko π ajsoym, joka pysähtyy ainakin niillä syötteillä, joissa esiintyy kirjain A?” on ratkeamaton.
Pienellä näppäryydellä saamme päättelyn toimimaan entistäkin
laajemmalle joukolle kysymyksiä.
Ennen sitä tulee huomata, että kahden edellisen tehtävän kysymyksistä
täsmälleen kaksi on ratkeavia.
Mitkä ne ovat?
Tämä kysymysOnko π ajsoym, joka
pysähtyy ainakin jokaisella syötteellä, jonka pituus on enintään kaksi ja
jossa esiintyy täsmälleen seitsemän A-kirjainta? ratkeaa tällä aliohjelmallaχ(π)
return T ja tämä kysymysOnko π ajsoym, joka pysähtyy ainakin jollakin syötteellä, jonka
pituus on enintään kaksi ja jossa esiintyy täsmälleen seitsemän
A-kirjainta? ratkeaa tällä aliohjelmallaχ(π)
return F.
Siis jokainen sellainen kysymys on ratkeava, jonka vastaus kaikille ajsoymeille on ”kyllä”. Tähän luokkaan kuuluva kysymys voi olla sillä tavalla vaativa, että voi olla vaikea huomata, että kysymys todellakin kuuluu tähän luokkaan. Silti jokaiselle sellaiselle kysymykselle on olemassa hyvin yksinkertainen testeri. Emme ehkä tiedä, että kysymys kuuluu siihen luokkaan, ja siksi emme tiedä, että ko. hyvin yksinkertainen testeri on sille kysymykselle pätevä testeri. Tietämättömyytemme ei kuitenkaan kumoa sitä, että se testeri on olemassa ja toimii oikein.
Myös jokainen sellainen kysymys on ratkeava, jonka vastaus kaikille ajsoymeille on ”ei”.
Henry Gordon Rice todisti väitöskirjassaan vuonna 1951, että nämä kaksi luokkaa kysymyksiä ovat ainoat ratkeavat kysymykset, jotka koskevat niiden syötteiden joukkoa, joilla annettu ajsoym pysähtyy. (Esimerkiksi kysymys ”Onko annetun ajsoymin koodissa ainakin 100 riviä” ei ole tällainen kysymys ja ratkeaa helposti.)
Lause 4 Jokainen seuraavat ehdot täyttävä kyllä/ei-kysymys on ratkeamaton: se koskee niiden syötteiden joukkoa, joilla annettu ajsoym pysähtyy, ja on olemassa sekä ajsoym jolle vastaus on ”kyllä” että ajsoym jolle vastaus on ”ei”.
Todistus. Oletamme, että kysymyksen ratkaiseva testeri τ on olemassa, ja rakennamme sen avulla pysähtymistesterin. Annamme niille kahdelle ajsoymille, joiden olemassa olo luvattiin lauseessa, nimet kyllä_ajsoym ja ei_ajsoym.
Aliohjelmalle surkea_otspt vastaus on joko ”kyllä” tai ”ei”.
Jos se on ”kyllä”, niin χ(π, σ) tekee ja testaa seuraavan ajsoymin:
ξπ, σ(ρ ∈ Σ*) ∈ 𝔹
π(σ)
return ei_ajsoym(ρ)
Jos π(σ) ei pysähdy, niin ξπ, σ käyttäytyy näinEi pysähdy millään syötteellä.
(Sen syöte on ρ.) eli samalla tavalla kuin tämä aliohjelmasurkea_otspt.
Sille ajsoymille testeri vastaa näinT, ja saman se vastaa ξπ, σ:lle
koska se käyttäytyy samoin.
Jos π(σ) pysähtyy, niin ξπ, σ(ρ):n suoritus pääsee kutsun π(σ) läpi
ja jatkaa eteenpäin, joten ξπ, σ käyttäytyy samalla tavalla kuin
tämä aliohjelmaei_ajsoym.
Sille ajsoymille testeri vastaa näinF, ja saman se vastaa ξπ, σ:lle
koska se käyttäytyy samoin.
Siksi tämä aliohjelmaχ(π, σ)
ξ := ξπ, σ
return ¬ τ(ξ) on pysähtymistesteri.
Huomasithan tämän yksityiskohdanτ(ξ) vastaa T silloin kun pysähtymistesteri vastaisi
F ja päinvastoin.
Tämä korjattiin negaatiolla ¬.?
Jos surkea_otspt:lle vastaus on ”ei”, niin χ(π, σ)
tekee ja testaa tämän ajsoyminξπ, σ(ρ ∈ Σ*) ∈ 𝔹
π(σ)
return kyllä_ajsoym(ρ).
Siis χ on tällainenχ(π, σ)
ξ := ξπ, σ
return τ(ξ).
Päättely, että χ on pysähtymistesteri, noudattaa jo tutuksi tullutta kaavaa.
Kummassakin tapauksessa, jos τ olisi olemassa, niin pysähtymistesterikin olisi olemassa, vastoin aiemmin todistettua. Niinpä τ ei ole olemassa. Todistuksen loppu on tapana merkitä viimeisen rivin oikeassa reunassa olevalla laatikolla. Tässä se on: □
Ratkeamattomuusilmiön tutkimista voi jatkaa moneen suuntaan. Ricen lauseen vuoksi melkein mikä tahansa niiden syötteiden joukkoa, joilla annettu aliohjelma pysähtyy, koskeva kyllä/ei-kysymys on ratkeamaton. On myös monia ratkeamattomia kyllä/ei-kysymyksiä, jotka koskevat jotakin muuta aihepiiriä kuin aliohjelmien käyttäytyminen.
Toinen suunta lähtee havainnosta, että jos kysymyksen ”pysähtyykö π tyhjällä syötteellä” vastaus on ”kyllä”, on aina mahdollista varmistua siitä että se on ”kyllä” käynnistämällä π ja odottamalla tarpeeksi kauan. Vastauksesta ”ei” voidaan toisinaan varmistua. Tiedämme esimerkiksi, että surkea_otspt ei pysähdy tyhjällä syötteellä. Ei kuitenkaan ole olemassa yleispätevää keinoa, jolla jokaisessa tapauksessa, jossa vastaus on ”ei”, voidaan varmistua siitä, että se todella on ”ei”. (Jos olisi, saataisiin tyhjän syötteen pysähtymistesteri käynnistämällä π:n suoritus ja ei-keino rinnakkain, ja odottamalla kunnes jompikumpi valmistuu.) On olemassa kyllä/ei-kysymyksiä, joissa kummallekaan vastaukselle ei ole yleispätevää varmistumiskeinoa.
Jos kysymys muutetaan muotoon pysähtyykö annettu aliohjelma annetulla syötteellä viimeistään annetun askelmäärän jälkeen, se muuttuu ratkeavaksi: aliohjelmaa voidaan suorittaa kunnes joko se pysähtyy tai annettu askelmäärä tulee täyteen. Voidaan todistaa, että ei ole olemassa yleispätevää keinoa saada tämän kysymyksen vastaus olennaisesti nopeammin kuin tällä tavalla. Vastaava tulos pätee kysymykselle pysähtyykö annettu aliohjelma annetulla syötteellä viimeistään käytettyään annetun määrän muistia.
Nämä tulokset yhdessä pysähtymistesterin olemattomuuden kanssa tarkoittavat, että ei ole olemassa olennaisesti parempaa yleispätevää keinoa selvittää mitä aliohjelma tekee kuin ajaa se ja katsoa mitä tapahtuu. Tämä on huono uutinen laadunvarmistuksen kannalta, koska erilaisia syötteitä on yleensä aivan liian monta, jotta ne kaikki voitaisiin kokeilla.