Keskustelu: Yleinen keskustelu: Pysähtymisongelmasta

Tiedän, että pysähtymisongelma on ratkeamaton eli siis ei löydy sellaista algoritmia, jotka ratkaisisivat sen kaikilla syötteillä. Kaikki vastaesimerkit, joita olen kirjallisuudesta löytänyt, perustuvat ikuisen silmukan hyödyntämiseen. Entä, jos olisi ohjelmointikieli, jossa ei sallittaisi ikuisia silmukoita, niin olisiko tällaisessa ohjelmointikielessä pysähtymisongelma ratkeava? Jos ei, niin miksi ei?

Ongelma on siinä, että silmukasta on vaikeaa sanoa päältä päin, onko se ikuinen silmukka vai päättyykö se joskus. Esimerkiksi kukaan ei tiedä seuraavasta silmukasta, päättyykö se kaikilla n:n alkuarvoilla:

# https://en.wikipedia.org/wiki/Collatz_conjecture
while n <> 1:
    if n%2 == 0:
        n = n/2
    else:
        n = n*3+1

Jos ohjelmointikielestä poistaa kokonaan while-silmukan ja muut rakenteet, joilla voi tehdä ikuisen silmukan (kuten rekursio), niin pysähtymisongelman voi ratkaista, koska jokainen ohjelma pysähtyy.

Ok. Eli ongelma pysähtymisongelman kanssa ovat vain ja ainoastaan ikuiset silmukat?

Niin voisi sanoa, minusta "ohjelma ei pysähdy" ja "ohjelma on ikuisessa silmukassa" tarkoittavat samaa.

Ikuinen silmukka ei ole ongelma. Jos ohjelmassa on ikuinen silmukka (”while true do nothing”), voidaan helposti todeta, että ohjelma ei pysähdy. Vastaavasti jos ohjelmassa ei ole yhtään silmukkaa tai kaikki silmukat ovat yksinkertaisia (esim. käydään läpi määrätyt luvut), on selvää, että ohjelma pysähtyy.

Ongelmana ovat silmukat, joissa on näennäisesti jokin lopettava ehto mutta joista ei ole mahdollista sanoa, toteutuuko ehto koskaan. Antti antoikin esimerkin: silmukka kyllä päättyy, jos n=1, mutta sisällön perusteella ei ole mahdollista sanoa, tapahtuuko näin kaikilla alkuarvoilla.

Idea ”ei sallittaisi ikuisia silmukoita” on alkuperäisen kysymyksen kannalta erikoisesti muotoiltu, koska koko pysähtymisongelmassa on kysymys siitä, voiko ikuisen silmukan tunnistaa. Toisin sanoen ajatuksestasi syntyisi ohjelmointikieli, jossa kääntäjän pitäisi hyväksyä vain ohjelmat, jotka taatusti pysähtyvät. Tässä kielessä siis pysähtymisongelmaan on varsin ilmeinen ratkaisu: kaikki ohjelmat pysähtyvät. Tällä ohjelmointikielellä ei kuitenkaan voisi tehdä esimerkiksi Antin edellä esittämää silmukkaa noin yleisessä muodossa, vaan silmukka vaatisi jonkinlaisia lisärajoitteita, jotta pysähtymisen voisi todistaa.

Jotkin todistuskielet ovat käytännössä funktionaalisia ohjelmointikieliä, joissa kaikki virhetilanteet pitää käsitellä ja ohjelman pysähtyminen todistaa. Ainakin algoritmisessä koodissa tällainen "melkein Turing-täydellinen" kieli on yllättävän käyttökelpoinen. Tyypillisistä rekursioista ja silmukoista näkee hyvin helposti, että ne päättyvät.

Esimerkin voisi toteuttaa päättyvästi funktiona f(n,max), joka palauttaa iteraatioiden lukumäärän, jos se on korkeintaan max, muuten -1.

Miten pysähtymisongelma onkaan todistettu? Wikipediassa on perinteinen todistus, jossa käytetään funktiota, joka pysähtyy tai ei pysähdy sen mukaan, mitä funktion ei pitäisi tehdä (pysähtyy kun ei pitäisi pysähtyä, ei pysähdy kun pitäisi). Onko tämä todistus kuitenkaan yleispätevä? Eikö voitaisi helposti määritellä pysähtymisentarkistusfunktiolle kolmas paluuarvo, jonka se saa tällaisissa epäselvissä tilanteissa? Vaikka mikä tahansa ohjelma tietysti joko pysähtyy tai ei pysähdy, voisi tarkistusfunktio kieltäytyä palauttamasta vastausta, jos tulos aiheuttaisi paradoksin. Funktio toimisi yhä kaikkiin ohjelmiin, mutta vain ulkopuolelta käsin, ei sisältä. Onko todistettu, ettei tällaista funktiota voi tehdä?

Todistuksessa käytetty paradoksaalinen esimerkki ei suinkaan ole ainoa. Moneen ratkaisemattomaan ongelmaan voi koodata triviaalin "ratkaisun", joka käy kaikki vaihtoehdot läpi ja joko löytää vastauksen äärellisessä ajassa tai ei pysähdy koskaan. Tällaisen ohjelman pysähtymiskysymys on sama kuin alkuperäisen mahdottoman ongelman ratkaiseminen, joten sitä ei voi toteuttaa.

Kolmen paluuarvon versio on tietysti mahdollinen, mutta on pakko olla äärettömästi tapauksia, joita se ei osaa ratkaista. Onkohan kukaan tutkinut, miten paljon niitä on suhteessa ratkeaviin tapauksiin mahdollisimman hyvällä toteutuksella?

jlaire kirjoitti:

Kolmen paluuarvon versio on tietysti mahdollinen, mutta on pakko olla äärettömästi tapauksia, joita se ei osaa ratkaista. Onkohan kukaan tutkinut, miten paljon niitä on suhteessa ratkeaviin tapauksiin mahdollisimman hyvällä toteutuksella?

Näin äkkiseltään luulisin, että kolmen paluuarvon ongelmia on ylinumeroituvasti mutta Turingin koneet ratkaisevat vain numeroituvan monta ongelmaa. Mutta ainakin mittateoriassa opetettiin, että ääretön/ääretön ei ole järkevällä tavalla määritelty, joten ehkä suhde ei ole kaikkein järkevin tapa mitata ongelmien lukumäärää.

Jos Turingin koneita on numeroituvasti (kuten niitä ymmärtääkseni on), voidaan määrittää

       ⎧ 0  jos i:nnettä Turingin konetta ei voida ratkaista
f(i) = ⎨        kahdella paluuarvolla
       ⎩ 1  muulloin

              n
              Σ  f(i)
             i=1
suhde = lim  ————————
        n→∞     n

Mutta onko olemassa tapaa tämän suhteen laskemiseksi?

fergusq kirjoitti:

Jos Turingin koneita on numeroituvasti (kuten niitä ymmärtääkseni on)

Turingin koneita on numeroituvasti mutta kolmen paluuarvon ongelmia on ylinumeroituvasti (koska esim. reaalilukuja on ylinumeroituvasti ja jokaisesta reaaliluvusta voidaan muodostaa ongelma, joka palauttaa 1 jos reaaliluvun 1. desimaali on 1, 2 jos 1. desimaali on 2 ja 3 jos 1. desimaali on vähintään 3). Suinkaan kaikki kolmen paluuarvon ongelmat eivät ole simuloitavissa Turingin koneella. Turingin konetta ei voi ratkaista vaan Turingin koneella voidaan osoittaa, onko joku teoria tai kieli ratkeava. Opiskeluaikana luin Friedin ja Jardenin kirjan Field Arithmetic, jossa asiaa käytiin läpi. Siinä ratkeavuutta oli sovellettu kuntateoriaan.

Mitä tarkoitat "kolmen paluuarvon ongelmalla"? Tässä keskustelussa kolme arvoa ovat siis true/false/unknown ja pysähtymisongelman osittain ratkaiseva funktio palauttaa jonkin niistä. Funktion parametrit ovat samat kuin tavallisessa true/false-pysähtymisongelmassa ja niitä on numeroituva määrä.