Kas olete kunagi mõelnud: mis täpselt on seade, millega seda artiklit loete? Mis on arvuti? Arvutiteadus pärineb juba ammu enne nende kaasaegsete arvutiseadmete mõtlemist. Valdkonnas, kus kõige sagedamini esitatavad küsimused keerlevad programmeerimiskeelte, -raamistike ja -raamatukogude ümber, võtame arvuti põhitõdesid sageli iseenesestmõistetavaks.

Kuid need arvutid, millel näib olevat lõpmatu potentsiaal - kas neil on mingeid piiranguid? Kas on probleeme, mida arvutid ei suuda lahendada?

Selles artiklis käsitleme neid küsimusi, eemaldudes programmeerimiskeelte ja arvuti arhitektuuride üksikasjadest. Mõistes arvutite ja algoritmide võimsust ja piiranguid, saame parandada oma mõtteviisi ja paremini põhjendada erinevaid strateegiaid.

Arvutamise abstraktne vaade annab ajaproovile vastu pidanud tulemusi, olles tänapäeval meie jaoks sama väärtuslik kui algselt 1970. aastatel välja töötatud.

Computabilidad

Mis on arvuti? Mis on probleem?

Koolis õpetatakse meile sageli probleemide ja funktsioonide vaimset mudelit, mis ütleb umbes nii:

Funktsioon on protseduur, mille rakendate sisendile x väljundi f (x) leidmiseks.

Tuleb välja, et matemaatiline määratlus on erinev:

Funktsioon on paaride komplekt, mis on järjestatud nii, et iga paari esimene element pärineb komplektist X (nimetatakse domeeniks), iga paari teine ​​element pärineb komplektist Y (nimetatakse kaasdomeeniks või vahemikuks) ja iga element domeen on ühendatud täpselt ühe vahemiku elemendiga.

Sellest piisas. Aga mida see täpselt tähendab?

See määratlus ütleb meile, et arvuti on funktsioonide arvutamise masin.

Miks?

Kuna arvutid muudavad suvalise sisendi mõneks väljundiks. Teisisõnu, nad lahendavad probleeme. Funktsioonide kaks määratlust, see, mida me väga hästi tunneme, ja formaalne, kattuvad paljudel praktilistel eesmärkidel.

Kuid matemaatiline määratlus võimaldab meil jõuda huvitavatele järeldustele, näiteks töötlemata funktsioonide olemasolu (see tähendab probleemid ilma lahenduseta):

Miks kõiki funktsioone ei saa kirjeldada kui algoritmi.

Mängureeglid

Oma argumentide hõlbustamiseks kujutleme arvuteid kui masinaid, millel on sisend, mis teostavad toimingute jada ja annavad mõne aja pärast väljundi.

Nimetagem sisestusmasina tähestikku, mis on mingi lõpliku hulga tähemärkide jada. Näiteks võib masina tähestik olla binaarne (0 ja 1) või see võib olla ASCII märgistik. Mis tahes piiratud tähemärkide jada on string - näiteks '0110'.

Samuti esindame masina tulemust binaarse aktsepteerimise ja tagasilükkamise otsusena, mis tehakse siis, kui masin (loodetavasti) oma arvutuse lõpetab. See abstraktsioon sobib hästi ülaltoodud funktsioonide matemaatilise määratlusega.

Neid parameetreid arvesse võttes on oluline iseloomustada veel üht tüüpi: tähemärkide kogu. Võib-olla tunneme muret stringide komplekti üle, mida masin aktsepteerib, või ehitame masinat, mis aktsepteerib stringe teatud komplektis, mitte teisi, või küsime võib-olla, kas on võimalik kujundada masinat, mis aktsepteerib kõiki konkreetses komplektis ja mitte teistes.

Kõigil neil juhtudel nimetatakse tähemärkide komplekti keeleks - näiteks kõigi paarisarvu tähistavate binaarsete stringide kogumiks või paarisarvuliste stringide komplektiks. Selgub, et keeled, nagu ka numbrid, võivad olla kaubeldakse operaatoritega nagu liitmine, liitumine, ristmik jms.

Oluline operaator on täheoperaator Kleene, mida kasutatakse ka regulaaravaldistega. Seda võib pidada kõigi võimalike keelevõimude ühendamiseks. Näiteks kui meie keel TO on märkide stringide komplekt {'01', '1'}, seejärel selle liige KOHALE * on tähemärgistring '0101111'.

Raamatupidamine

Mõistatuse viimane tükk enne meie väite tõendamist, et kõik funktsioonid pole arvutatavad, on raamatupidamise mõiste. Intuitiivselt näitab meie test, et keeli on rohkem; ehk nende lahendamiseks rohkem probleeme kui võimalikke programme. See töötab, sest probleem, kas tähemärk kuulub keelde (jah / ei), on iseenesest probleem.

Täpsemalt öeldes ütleb meie test, et võimalike programmide kogum on lõpmatult loendatav, samas kui tähestikus olevate keelte hulk on lõpmatu loendamatu.

Siinkohal võite mõelda: 'Lõpmatus on iseenesest üsna kummaline idee, nüüd on mul kaks neist lahendada!'

Noh, see pole nii hull. Loendamatult lõpmatu hulk on see, mida saab loendada. Võib öelda: see on esimene element, see on teine ​​element ja nii edasi, määrates lõpuks hulga igale elemendile numbri. Võtame näiteks paarisarvude hulga. Võime öelda, et 2 on esimene, 4 teine, 6 kolmas ja nii edasi. Sellised komplektid on loendatavad lõpmatud või loendatavad.

Mõne hulga puhul, nagu tegelikud arvud, pole aga vahet, kui tark sa oled; loendust lihtsalt pole. Need komplektid on lugematu arv lõpmatuid või loendamatu.

Paljud raamatupidamisprogrammid

Kõigepealt tahame näidata, et arvutiprogrammide komplekt on loendatav. Oma eesmärkidel teeme seda, jälgides, et kõigi tähemärkide string piiratud tähestiku kohal on loendatav. See töötab, kuna arvutiprogrammid on piiratud tähemärgistringid.

Tõend see on lihtne ja me ei käsitle siin üksikasju. Põhipunkt on see, et arvutiprogramme on sama palju kui näiteks loomulikke numbreid.

Kordamiseks:

Kõigi tähestiku märkide stringide komplekt (nt. Kõigi arvutiprogrammide komplekt) on loendatav.

Lugematud paljud keeled

Seda järeldust arvestades, kuidas on nende märgistringide alamhulkadega? Küsiti muul viisil, kuidas on kõigi keelte komplektiga? Selgub, et see komplekt on loendamatu.

Kõigi keelte komplekt mis tahes tähestikus on loendamatu.

Veelkord, me ei kajasta tõend siin.

Tagajärjed

Ehkki need ei pruugi kohe silma paista, on lugematute keelte ja kõigi arvutiprogrammide arvestuse tagajärjed sügavad.

Miks?

Oletame TO on ASCII märgistik; ASCII tähemärgid need on vajalikud ainult arvutiprogrammi koostamiseks. Näeme, et stringide komplekt, mis esindab näiteks JavaScripti programme, on selle alamhulk KOHALE * (siin on * Kleene täheoperaator). JavaScripti valik on meelevaldne. Kuna see programmide komplekt on loendatava hulga alamhulk, on meil JavaScripti programmide komplekt loendatav.

Mõelgem sellele ka mis tahes keele puhul L saame määratleda mõne funktsiooni f mille väärtuseks on 1 string x See on sees L ja 0 muul juhul. Kõik need funktsioonid on erinevad. Kuna kõigi keelte hulgaga on 1: 1 vastavus ja kuna kõigi keelte hulk on loendamatu, on meil kõigi nende funktsioonide hulk loendamatu.

Siin on punkt põhjalikult:

Kuna kõigi kehtivate programmide komplekt on loendatav, kuid funktsioonide komplekt mitte, siis peavad olema mõned funktsioonid, mille jaoks me lihtsalt ei saa programme kirjutada.

Me ei tea endiselt, kuidas need funktsioonid või probleemid välja näevad, kuid me teame, et need on olemas. See on alandlik tõdemus, sest on probleeme, millele pole lahendust. Peame arvuteid ülimalt võimsateks ja võimekateks, kuid mõned asjad jäävad neile kättesaamatuks.

Nüüd on küsimus: 'Millised need probleemid on?' Enne nende probleemide kirjeldamise jätkamist peame arvutamise üldistavalt modelleerima.

Turingi masinad

Üks esimesi arvuti matemaatilisi mudeleid töötas välja Alan Turing. See mudel, mida nimetatakse Turingi masinaks, on äärmiselt lihtne seade, mis haarab täielikult meie arusaama arvutatavusest.

Masina sisendiks on lint, millele sisend on kirjutatud. Kasutades lugemis- / kirjutamispead, teisendab masin sisendi väljundiks mitmete sammude kaudu. Igal sammul otsustatakse, kas ja mida lindile kirjutada ning kas liikuda paremale või vasakule. Selle otsuse aluseks on täpselt kaks asja:

• Praegune sümbol pea all ja

• Masina sisemine olek, mida värskendatakse ka sümbolit sisestades

See on kõik.

Universaalsus

Aastal 1926 arendas Alan Turing lisaks Turingi masinale ka arvukate arvutite olemuse kohta mitu olulist ideed, kirjutades oma kuulsa artikli 'Arvutatavatest numbritest'. Ta mõistis, et arvutiprogrammi ennast võib vaadelda kui arvuti sisendit. Sellest vaatenurgast oli tal ilus mõte, et Turingi masin suudaks seda sisendit simuleerida või teostada.

Kui me võtame neid ideid täna iseenesestmõistetavana, siis Turingi ajal oli sellise universaalse masina idee läbimurre, mis võimaldas Turingil arendada lahendamatuid probleeme.

Kiriku-Turingi lõputöö

Enne jätkamist uurime olulist punkti: me teame, et Turingi masin on arvutusmudel, kuid kas see on piisavalt üldine? Sellele küsimusele vastamiseks pöördume Kiriku-Turingi lõputöö , mis annab kinnitust järgmisele väitele:

Kõik arvutatav on Turingi masina abil arvutatav.

Kui Turing töötas Turingi masina välja arvutusmudelina, töötas Alonzo Church välja ka arvutusmudeli, mida tuntakse lambda-arvutusena. Need mudelid on võimsad selle poolest, et mõlemad kirjeldavad arvutust ja teevad seda viisil, mis on sama mis tahes tänapäeva arvuti või mis tahes arvuti puhul. See tähendab, et me võime kasutada Turingi masinat lahendamata probleemide kirjeldamiseks, teades, et meie leiud kehtivad kõigi võimalike arvutite kohta.

Tunnustatavus ja otsustatavus

Enne lahendamatu probleemi konkreetset kirjeldamist, nimelt keeletuvastajate mõisted ja keelt otsustavad tegurid, peame käsitlema veidi põhjalikumalt.

Keel on äratuntav, kui on olemas Turingi masin, mis selle ära tunneb.

Y

Keel on otsustatav, kui selle otsustab mõni Turingi masin.

Keele tuvastamiseks peab Turingi masin aktsepteerima kõiki keelelisi tähemärke ja ei tohi aktsepteerida midagi, mida selles keeles pole. Võite need stringid tagasi lükata või korrata. Otsusteguriks saamiseks peab Turingi masin alati oma sisendi lõpetama aktsepteerimise või tagasilükkamisega.

Siin on sisenemise peatamise idee kriitiline. Tegelikult näeme, et otsustustegurid on võimsamad kui äratundjad. Lisaks saab probleemi lahendada või teisiti öelda, funktsioon on otsustatav ainult siis, kui on olemas Turingi masin, mis otsustab funktsiooni kirjeldatud keele.

Otsustamatus

Kui olete kunagi arvutiprogrammi kirjutanud, peate kindlasti teadma, mis tunne on seal istuda, lihtsalt vaadates, kuidas arvuti programmi töötades rattaid keerutab. Ei ole teada, kas programm võtab kaua aega või on koodis mingi viga, mis põhjustab lõpmatu tsükli. Võib-olla olete isegi mõelnud, miks kompilaator ei kontrolli koodi, et näha, kas see peatub või kordub igaveseks, kui see töötab.

Koostajal pole sellist juhtimist, sest seda lihtsalt ei saa teha. Asi pole selles, et kompileerimisinsenerid pole piisavalt targad või neil pole ressursse, lihtsalt suvalist arvutiprogrammi on võimatu kontrollida, kas see peatub.

Saame seda testida Turingi masina abil. Turingi masinaid võib kirjeldada kui karakterikeeli, nii et neid on loendamatu arv. Oletame, et M_üks, M₂ja nii edasi moodustavad kõigi Turingi masinate komplekti. Määratleme järgmise funktsiooni:

f (i, j) = 1 si M_isa nõustudj>, 0 vastupidi

Siin on 'M stringi kodeerimise' süntaks ja see funktsioon kujutab endast probleemi 1 tekitamist, kui M_ipeatub M aktsepteerimisel_jsisendina ja väljundina 0 vastupidi. Pange tähele, et M_ipeab peatuma (st olema diilirikkuja). See on vajalik, kuna me tahame kirjeldada otsustamatut funktsiooni (see tähendab probleemi ilma lahenduseta).

Määratleme nüüd ka keel L mis koosneb Turingi masina stringikodeeringutest, mis EI aktsepteeri nende enda kirjeldusi:

L =

Näiteks mõni masin M_ükssaab sisendiks väljastada 0üks& gt, samal ajal kui teine ​​masin M₂võib anda sisendiks väljundi 12>. Selle keele otsustamatuse tõestamiseks küsime, mida teeb M_L, masin, mis otsustab keele L, kui talle antakse oma kirjeldusL> sisendina. On kaks võimalust:

M_Lsa nõustudL>

või

M_LeitabL>

Si M_Laktsepteerib oma kodeeringut, nii et see tähendabL> ei ole keeles L. Kuid kui see nii oli, siis M_LMa poleks pidanud teie kodeeringut kõigepealt aktsepteerima. Teisalt, kui M_Lei aktsepteeri siis enda kodeeringutL> on L-keeles, siis M_Lsee oleks pidanud aktsepteerima teie stringi kodeeringut.

Mõlemal juhul on meil paradoks või matemaatilises mõttes vastuolu, mis näitab, et L-keel on otsustamatu; seetõttu oleme kirjeldanud oma esimest lahendamatut probleemi.

Probleemi peatamine

Kuigi äsja kirjeldatud probleem ei pruugi tunduda asjakohane, võib selle taandada täiendavatele praktilise tähtsusega lahendamatutele probleemidele, eriti kinnipidamise probleem :

Türingu masinakodeeringute keel, mis peatub tühjal stringil.

Peatumisprobleem kehtib küsimusele, miks kompilaatorid ei suuda lõpmatuid sõlme varakult tuvastada. Kui me ei suuda kindlaks teha, kas programm lõpeb tühja stringiga, siis kuidas saaksime kindlaks teha, kas selle käivitamise tulemuseks on lõpmatu sõlm? Siinkohal võib tunduda, et lehvitasime käega, et jõuda lihtsale järeldusele, kuid mõistsime, et ükski Turingi masin ei suuda öelda, kas arvutiprogramm peatub või jääb igavesti sõlme. See on praktiliste rakenduste puhul suur probleem ja seda ei saa lahendada Turingi masinas ega muud tüüpi arvutis. IPhone ei saa seda probleemi lahendada. Paljude tuumadega töölaud ei saa seda probleemi lahendada. Pilv ei suuda seda probleemi lahendada. Isegi kui keegi tahaks kvantarvutit leiutada, ei suuda ta ikkagi peatusprobleemi lahendada.

Kokkuvõte

Arvutatavuse teooria uurimisel oleme näinud, kuidas on palju funktsioone, mida pole loendamisargumendi abil võimalik selle sõna üheski tavamõistes arvutada. Me määratleme täpselt, mida me arvutamise all mõtleme, pöördudes tagasi Turingi inspiratsiooni tema enda kogemustest pliiatsi ja paberiga, et vormistada Turingi masin. Oleme näinud, kuidas see mudel suudab arvutada välja kõik, mida saab ükskõik milline praegune või homseks kavandatud arvuti, ja mõistsime klassi probleemidest, mis pole üldse arvutatavad.

Sellegipoolest on arvutatavusel varjukülg. See, et suudame probleemi lahendada, ei tähenda, et saaksime selle kiiresti lahendada. Lõppude lõpuks, mis kasu on arvutist, kui selle arvutamine ei lõpe enne, kui päike tulevikus meie jaoks kümneid miljoneid aastaid nova muudab?

Jättes arvutuslikud funktsioonid ja keeled seljataha, arutame nüüd arvutuse keerukust, uurime tõhusat arvutust ja kuulsat P vs. NP.

Keerukus

Aeglane vs. Kiire

Arvutiteadlased tunnustavad mitmesuguseid probleemiklasse ja kaks meile olulist klassi hõlmavad probleeme, mida arvutid saavad kiiresti või tõhusalt lahendada, mida nimetatakse P ja probleemid, mille lahendusi on võimalik kiiresti kontrollida, kuid mida ei saa kiiresti saavutada, nn Näiteks .

Oletame näiteks, et vastutate veebis tutvumisteenuse algoritmide väljatöötamise eest ja keegi esitab küsimuse: 'Kas kõik saavad kuupäeva saada?' Vastus taandub kokkusobivate üksikisikute sobitamisele, nii et kõik sobivad. Selgub, et selle probleemi lahendamiseks on olemas tõhusad algoritmid. See probleem on komplektis P .

Mis oleks, kui me tahaksime oma kasutajate seas välja selgitada suurima vennaskonna? Vennaskonna all peame silmas suurimat üksteisega ühilduvate inimeste võrku. Kui kasutajate arv on väike, saab selle probleemi kiiresti lahendada. Saame hõlpsasti tuvastada näiteks 3 kasutajaga gildi. Kui aga hakkame otsima suuremaid korporatsioone, on probleemi lahendamine üha raskem. See probleem on komplektis Näiteks .

Ametlikud mõisted

P on hulk probleeme, mida saab lahendada polünoomiajas. See tähendab, et arvutuslike sammude arv on probleemi suuruse suhtes piiratud polünoomifunktsiooniga. Me teame, et küsimus „Kas kõik saavad kohtingutele tulla?” Tuntud ka kui kahepoolne kokkulangevusprobleem , See on sees P .

Näiteks on probleemide kogum, mida on polünoomiajal võimalik kontrollida. See hõlmab loomulikult kõiki P probleeme; me ei tea siiski, kas see piiramine on range. Me teame probleeme, mis on tõhusalt kontrollitavad, kuid mida ei saa tõhusalt lahendada, kuid me ei tea, kas probleem on tõesti lahendamatu. Vennaskonna probleem on üks neist probleemidest. Me teame, et suudame lahendust tõhusalt kontrollida, kuid ei tea kindlalt, kas suudame probleemi tõhusalt lahendada.

Viimaseks NP-täielik on probleemide kogum, milles on kõige raskemad probleemid Näiteks . Neid tuntakse kui kõige raskemaid, kuna kõik probleemid on Näiteks saab tõhusalt ümber kujundada NPC . Selle tagajärjel, kui keegi tuvastas aadressi probleemile tõhusa lahenduse NPC , igasugu Näiteks neelduks P . Vennaskonna probleem on ka aastal NPC

Seega jõuame probleemini P vastu Näiteks . Paljud arvutiteadlased ja matemaatikud usuvad seda kindlalt P Y Näiteks nad pole ühesugused. Kui need oleksid, oleks tagajärjed üle jõu käivad. Suur osa tänasest digitaalsest infrastruktuurist põhineb sellel, et seal on probleeme Näiteks mida pole P . Kui see nii ei oleks, lagunevad näiteks krüptograafilised meetodid üleöö, võimaldades inimesel, kellel on tõhus probleem NPC suudab õõnestada ka kõige rangemaid turvaprotokolle.

Jälgitavuse peensused

Arvuti algajate jaoks ei tundu vahe matšimise ja gildi probleemide vahel kuigi suur probleem. Tegelikult on erinevus probleemi vahel P ja probleem aastal Näiteks see võib olla väga peen. Võimalus vahet teha on oluline kõigile, kes algoritme reaalses maailmas kujundavad.

Mõelge lühima tee probleemile. Arvestades kahte asukohta, on eesmärk kindlaks teha nende vahel lühim tee. IPhone arvutab selle välja millisekundite jooksul. See on arvutuslikult ravitav probleem.

Teisest küljest võtke arvesse häkkerite probleemi, kus eesmärk on külastada võimalike sihtkohtade alamhulka, mis jõuavad võimalikult lühikese vahemaa tagant lähtekohta. See probleem sarnaneb lühima tee probleemiga, kuid on NP-täielik; see selgitab ka seda, miks tarneahelalogistika on miljard dollarit.

Tegelikult võime olla veelgi peenemad. Lühima tee (P) küsimise asemel võime küsida pikimat teed ilma sõlmedeta. Selgub, et ka pikima tee probleem on NP-täielik.

Selle peene eristamise kohta on veel palju näiteid, sealhulgas tippude katete tuvastamine kahepoolses vs. üldised või rahuldavad Boole'i ​​valemid kahe ja kolme literaaliga ühe lause kohta. Asi on selles, et pole kohe selge, kas probleem on P-s või NP-s, seega on käituse analüüsi põhjus kriitiline oskus. Kui algoritm, mille peab välja töötama, on seotud P-ga seotud probleemiga, siis teame, et on olemas tõhus lahendus. Kui seevastu on probleem NP-s, siis on meil tugev argument, et lahenduse otsimisele vastu vaielda, sest üldiselt võtaks algoritm probleemi lahendamiseks liiga kaua aega.

Kokkuvõte

Selles keerukustestis määratleme probleemiklassid P ja NP. P esindab mitteametlikult probleeme, mida arvuti saab tõhusalt lahendada, samas kui NP esindab tõhusalt kontrollitavaid.

Keegi pole suutnud näidata, et P pole võrdne NP-ga. Kui need kaks probleemide klassi on samaväärsed, on see nn P vs. NP ja see on tänapäeval teoreetilise arvutamise kõige olulisem avatud probleem, kui mitte kogu matemaatika. Tegelikult nimetas savimatemaatika instituut 2000. aastal probleemi P vs. NP kui üks matemaatika seitsmest kõige olulisemast lahtisest küsimusest ja on pakkunud miljoni dollari suurust tasu testi eest, mis määrab selle probleemi lahenduse.

järeldus

Selles artiklis süveneme arvutatavuse ja keerukuse valdkonda, vastates suurtele küsimustele nagu 'Mis on arvuti?' Kuigi üksikasjad võivad olla ülekaalukad, tasub meeles pidada mitmeid põhjalikke õppusi:

• On asju, mida lihtsalt ei saa arvutada, näiteks peatusprobleem.

• On asju, mida ei saa tõhusalt arvutada, näiteks probleemid NPC-s.

Üksikasjadest olulisemad on arvutusviisid ja arvutusprobleemid. Professionaalses elus ja isegi igapäevaelus võime kokku puutuda kunagi varem näinud probleemidega ning kasutada tõestatud tööriistu ja tehnikaid parima tegutsemisviisi määramiseks.