Lopeta ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Pysäytysongelma on yksi algoritmien teorian ongelmista [1] , joka voidaan epävirallisesti ilmaista seuraavasti:

Menettelyn kuvaus ja sen alkusyöttötiedot annetaan. On määritettävä: loppuuko toimenpiteen suorittaminen näillä tiedoilla koskaan; tai että toimenpide suoritetaan koko ajan pysähtymättä.

Alan Turing osoitti vuonna 1936 , että pysäytysongelma on ratkaisematon Turingin koneessa . Toisin sanoen tämän ongelman ratkaisemiseksi ei ole yleistä algoritmia. [2]

Pysäytysongelma on keskeinen laskettavuusteoriassa, koska se on ensimmäinen esimerkki ongelmasta, jota ei voida ratkaista algoritmisesti.

Toimintojen suhteen ongelma voidaan kuvata helposti seuraavasti:

Jokaiselle funktiolle F(G, aloitustila), joka voi määrittää, pysähtyykö toinen funktio, voit aina kirjoittaa funktion G(aloitustila), joka, kun se välitetään F:lle, saa päinvastaisen suorituksen tuloksen kuin F ennustaa.

Moniin muihin tehtäviin[ mitä? ] voidaan todistaa niiden algoritminen ratkaisemattomuus yrittämällä pelkistää ne pysäytysongelmaan. Tämä tehdään kaavion mukaan "päinvastoin": olkoon tietty ongelma, jonka ratkaisemattomuus on määritettävä. Sitten oletetaan, että se on ratkaistavissa, ja yritämme tätä tosiasiaa käyttäen kirjoittaa algoritmi tämän ongelman pysäytysongelman ratkaisemiseksi. Jos tämä onnistuu, joudumme ristiriitaan, koska tiedetään, ettei pysäytysongelman ratkaisemiseksi ole algoritmia. Tämä tarkoittaa, että olettamus oli väärä ja alkuperäinen ongelma on myös ratkaisematon.

Todiste

Harkitse joukkoa algoritmeja, jotka ottavat luonnollisen luvun syötteenä ja antavat myös luonnollisen luvun lähtönä. Valitaan jokin Turingin täydellinen ohjelmointikieli. Jokainen algoritmi voidaan kirjoittaa äärellisenä merkkijonona tällä kielellä. Järjestetään joukko (tämä on mahdollista, koska se on äärellisen joukon alkioiden äärellisten jonojen joukko ja siksi laskettava ), ja jokainen algoritmi saa oman sarjanumeronsa. Kutsukaamme analysaattoria hypoteettiseksi algoritmiksi, joka vastaanottaa syötteenä luonnollisten lukujen parin ja: $S$ $S$ $(N,X)$

pysähtyy ja palauttaa 1, jos algoritmi numerolla ei pysähdy vastaanottamisen jälkeen $N$ $X$
ei pysähdy muuten (jos algoritmi numerolla pysähtyy vastaanottamisen jälkeen ). $N$ $X$

Pysäytysongelma voidaan muotoilla uudelleen seuraavasti: Onko analysaattoria olemassa?

Lause. Analysaattoria ei ole olemassa.

Todistetaan se ristiriitaisesti. Oletetaan, että Analyzer on olemassa. Kirjoitetaan Diagonalizer-algoritmi, joka ottaa syötteeksi luvun , välittää parin argumentteja analysaattorille ja palauttaa työnsä tuloksen. Toisin sanoen, diagonalizer pysähtyy silloin ja vain, jos algoritmi numerolla ei pysähdy vastaanotettuaan numeron syötteenä . Antaa olla järjestysnumero Diagonalizer joukossa . Suorita Diagonalizer välittämällä tämä numero sille . Diagonalisaattori pysähtyy, jos ja vain jos algoritmi, jolla on luku (eli se itse) ei pysähdy, kun se vastaanottaa syötteenä luvun (jonka välitimme sille). Tästä ristiriidasta seuraa, että olettamuksemme on väärä: Analysaattoria ei ole olemassa, mikä oli todistettava. $N$ $(N,N)$ $N$ $N$ $K$ $S$ $K$ $K$ $K$

Katso myös

Ohjausvuokaaviota voidaan käyttää luokitteluun nopeasti, kun ohjelmassa ei ole silmukoita (ja siksi se pysähtyy), siinä on triviaaleja silmukoita (ja siksi pysähtyy), ei-triviaalisia silmukoita (ei ratkea) tai se siirtyy äärettömään silmukkaan.

Muistiinpanot

↑ N.K. Vereshchagin, A. Shen Luentoja matemaattisesta logiikasta ja algoritmien teoriasta. Osa 3. Laskettavat funktiot Arkistoitu 12. marraskuuta 2015 Wayback Machinessa
↑ Turing A. On Computable Numbers, Entscheidungsproblem -sovelluksella // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Voi. s2-42, Iss. 1. - s. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230 (tässä julkaisussa Turing esittelee Turingin koneen määritelmän , muotoilee ripustusongelman ja osoittaa, että se, kuten resoluutioongelma , on ratkaisematon).

Linkit

c2:Pysäytysongelma
Jäätymisongelma _