Loop variantti

FONT SIZE:
fontsize_dec
fontsize_inc
Elokuu 8, 2016 Joel Manner L 0 3

Tietotekniikassa, silmukka muunnos on matemaattinen funktio määritelty tila-avaruus tietokoneohjelman, jonka arvo on monotonisesti vähentynyt suhteessa perusteltu suhteessa mukaan iterointia taas silmukan joissakin muuttumattoman olosuhteissa, varmistaen näin sen irtisanominen. Silmukka variantti, jonka alue rajoittuu ei-negatiivisia kokonaislukuja tunnetaan myös sidottu funktiona, koska tässä tapauksessa se tarjoaa triviaali ylärajan toistojen silmukan ennen päättyy. Kuitenkin, silmukka variantti voi olla transfinite, ja näin ollen ei välttämättä rajoitu kokonaislukuina.

Perusteltu suhde on ominaista olemassa minimaalinen osa jokaisen ei-tyhjä osajoukko toimialallaan. Olemassaolo variantti osoittaa päättymisestä, kun silmukan tietokoneohjelman perusteltu laskeutuminen. Perusominaisuus perusteltu suhde on, että se ei ole ääretön laskeva ketjuja. Näin ollen silmukka, jolla variantti päättyy, kun äärellinen määrä iteraatioiden, niin kauan kuin sen runko päättyy joka kerta.

Kun taas silmukka, tai yleisemmin, tietokoneohjelma, joka voi sisältää vaikka silmukoita, sanotaan olevan täysin oikea, jos se on osittain oikea ja se päättyy.

Sääntö päättely täydellistä oikeellisuudesta

Jotta virallisesti todeta oikeusvaltion päättelyn varten päättymisestä while-silmukka olemme osoittaneet edellä, muistaa, että Floyd-Hoare logiikka, sääntö ilmaista osittainen oikeellisuus kun silmukka on:

jossa I on invariantti, C on kunnossa, ja S on elin silmukan. Ilmaista yhteensä oikeellisuudesta, kirjoitamme sen sijaan:

jossa lisäksi V on variantti, ja sovitun käytännön sitoutumaton symboli z on pidetty yleisesti määrällisesti.

Jokainen silmukka, joka päättyy on variantti

Olemassaolo variantti merkitsee sitä, että vaikka silmukka päättyy. Se saattaa tuntua yllättävältä, mutta päinvastainen on totta, samoin, kunhan oletamme Axiom valinta: jokainen samalla silmukka, joka päättyy on variantti. Tämän todistamiseksi oletetaan, että silmukka

Syöttönäppäimellä lopetetaan koska muuttumaton I, jossa meillä on yhteensä oikeellisuutta väite

Harkitse "seuraaja" suhteessa valtion tilan aiheuttama suorittamisesta lausunnon S: valtio täyttää sekä muuttumaton I ja ehto C. Siis meidän sanoa, että valtio on "seuraaja" ja jos ja vain jos

  • Minä ja C ovat molemmat totta valtion ja
  •  on valtio, joka syntyy suorittamisesta lausuman S tilassa

Toteamme, että muutoin silmukka epäonnistuu lopettaa.

Seuraavaksi tarkastellaan refleksiivinen, transitiivinen sulkeminen "seuraaja" suhteen. Soita Tämä tapaus: sanomme, että valtio on toistaa ja jos jompikumpi tai on rajallinen ketju sellainen, että ja on "seuraaja" ja kaikilla i,

Toteamme, että jos ja ovat kaksi eri valtiota, ja on toistaa on, niin ei voi olla toistaa julkaisusta uudelleen, muuten silmukka epäonnistuu lopettaa. Toisin sanoen, iteraatio on antisymmetrinen, ja siten, osittainen järjestyksessä.

Nyt, koska while-silmukka päättyy jälkeen rajallinen määrä annettuja ohjeita muuttumaton I, eikä valtio on seuraaja ellen on totta, että valtion, voimme päätellä, että jokaisella valtiolla on vain äärellisen monta toistetaan, jokainen laskeva ketju suhteen iterointia on vain äärellisen monta eri arvoja, joten ei ole ääretön laskeva ketju, eli silmukka iteraation täyttää laskeva ketju kunnossa.

Siksi olettaen selviö valinta "seuraaja" suhteessa alunperin määritelty silmukka on perusteltu valtion avaruus koska se on tiukka ja sisältyvät "toistaa" suhteen. Näin identiteetti toiminto tämän tila-avaruus on muunnos while-silmukka, kuten olemme osoittaneet, että valtion on tiukasti pienenee "seuraaja" ja "toistaa" joka kerta runko S suoritetaan annetaan muuttumaton I ja kunto C.

Lisäksi voimme osoittaa jonka laskenta väite, jonka olemassaolo muunnoksia merkitsee olemassaolon variantin ω1, ensimmäinen lukematon järjestysluvut, eli

Tämä johtuu siitä, että kokoelma kaikkien valtioiden pääsee rajallinen tietokoneohjelman rajallinen määrä askeleen päässä rajallinen tulo on numeroituvasti ääretön, ja ω1 on luettelointi kaiken oikein kertaluvun tyyppejä numeroituva sarjaa.

Käytännön näkökohdat

Käytännössä silmukka vaihtoehdot katsotaan usein ei-negatiivisia kokonaislukuja, tai jopa tarvitse olla niin, mutta vaatimus siitä, että jokainen silmukka on kokonaisluku muunnos poistaa ilmaisuvoimaa rajaton iteroinnin peräisin ohjelmointikieli. Ellei tällainen kielen avulla transfinite todiste lopettamisesta muilla yhtä voimakkaita konstruktio kuten rekursiivinen funktio puhelun, se ei enää pysty täysin μ-rekursio, mutta vain alkeellinen rekursio. Ackermann tehtävänä on kanoninen esimerkki rekursiivinen toiminto, joka ei voi lasketaan silmukka kokonaisluku variantti.

Mitä niiden laskennallisen kuitenkin, toiminnot eivät ole primitiivinen rekursiivinen valhe kaukana valtakunnassa mitä pidetään yleensä taipuisa. Harkitsee jopa yksinkertaisesti kyse eksponenttilausekkeet kuin primitiivinen rekursiivinen funktio, ja että koostumus primitiivisen rekursiiviset funktiot on alkeellinen rekursiivinen, voi alkaa nähdä kuinka nopeasti alkeellinen rekursiivinen funktio voi kasvaa. Ja mikä tahansa toiminto, joka voidaan laskea Turingin koneen käyntiaika joita rajoittaa alkeellinen rekursiivinen funktio on itse primitiivinen rekursiivinen. Joten on vaikea kuvitella käytännön hyötyä koko μ-rekursio jossa primitiivinen rekursio ei tehdä, varsinkin kun entinen voidaan simuloida jälkimmäinen jopa tavattoman pitkä käynnissä kertaa.

Ja joka tapauksessa, Kurt Gödel ensimmäinen keskeneräisyys lause ja pysäyttää ongelma tarkoita, että on olemassa vaikka silmukoita että aina lopettaa, mutta ei voida osoittaa tekemään niin; Näin se on väistämätöntä, että mitään vaatimusta virallisia todisteita sopimuksen irtisanomisesta on vähentää ilmaisuvoimaa ohjelmointikieli. Vaikka olemme osoittaneet, että jokainen silmukka, joka päättyy on variantti, tämä ei tarkoita, että hyvin perusteltu, silmukan iteraation voidaan osoittaa.

Esimerkki

Tässä on esimerkki, C-kuin pseudokoodina, on kokonaisluku muunnos laskea joitakin ylärajan määrää toistojen jäljellä while-silmukka. Kuitenkin C mahdollistaa sivuvaikutuksia arvioinnissa ilmaisuja, mikä ei ole hyväksyttävää kannalta virallisesti tarkastaa tietokoneohjelman.

Miksi edes harkita kuin kokonaisluku variantti?

Miksi edes harkita kuin kokonaisluku tai transfinite variantti? Tämä kysymys on esitetty, koska kaikissa käytännön tapauksissa, joissa haluamme todistaa, että ohjelma päättyy, haluamme myös osoittaa, että se päättyy kohtuullisessa ajassa. On olemassa ainakin kaksi mahdollisuutta:

  • Yläraja toistojen silmukan voi olla edellytyksenä todistaa irtisanomisen ensimmäinen paikka. Voi olla toivottavaa erikseen osoittaa kolme ominaisuudet
    • osittainen oikeellisuus,
    • irtisanominen, ja
    • käyntiaika.
  • Yleispätevyyttä: harkitsee transfinite vaihtoehtoja mahdollistaa kaikki mahdolliset todisteet irtisanomisen jonkin aikaa silmukka nähtäväksi kannalta olemassaolosta variantti.
  0   0
Edellinen artikkeli Olipa kerran ... Ihminen
Seuraava artikkeli Forameniin spinosum

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha