Računski model

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Računski model je teoretični model računalnika. Računske modele razdelimo na standardne in nestandardne. Po domače povedano šteje za standarni tak model, ki ga načeloma lahko realiziramo v obliki mehanizma ali avtomata, ki zaporedno izvaja posamezne korake.

Opomba: računske modele, pri katerih se več operacij izvaja hkrati, štejemo za standardne v primeru, da so je računski postopek natančno določen (na primer, kaj se bo zgodilo ni odvisno od slučaja). Primer takega modela so računska vezja.

Vsebina

Standardni modeli

Standardne modele lahko razvrstimo v univerzalne in specialne.

Univerzalni modeli

Univerzalni modeli se odlikujejo po tem, da so najbolj zmogljivi računski modeli, ki bi jih načeloma lahko dejansko realizirali. Univerzalni modeli lahko simulirajo široko množico drugih modelov, med drugim lahko vsak univerzalni model simulira vse druge univerzalne modele. Od tod sledi, da so vsi med seboj ekvivalentni in da lahko z vsakim od njih rešimo isti razred problemov. Med standardne univerzalne modele računanja uvrščamo:

Vsak od teh modelov ima natančno matematično definicijo. Mogoče je tudi dokazati, da je vsak problem, ki ga je mogoče rešiti z enim od standardnih univerzalnih modelov, mogoče rešiti tudi s katerimkoli drugim standardnim univerzalnim modelom računanja. Še več, tudi računska zahtevnost se pri tem spremeni kvečjemu za polinomski faktor, glej polinomska prevedljivost.

Znana je Churcheva teza, ki pravi, da je vse, kar je možno izračunati v intuitivnem smislu, mogoče izračunati z enim od standardnih univerzalnih modelov računanja in obratno.

Standardni univerzalni model računanja uporabimo pri opisu algoritmov, saj je to takšna računska procedura, ki jo je možno izvesti s standardnim univerzalnim računskim modelom. Pri tem dodatno zahtevamo, da se procedure pri veljavnih vhodnih podatkih ustavi in vrne rezultat v končno mnogo računskih korakih.

Specialni modeli

Za razliko od univerzalnih modelov računanja je specialni model računanja namenjen reševanju posebnih (omejenih) problemov. Med specialne modele računanja uvrščamo:

Nestandardni modeli

Nestandardni modeli računanja vključujejo v opisu računskega stroja pojme, kot je nedeterminiziem, verjetnostno računanje in oraklji.

Glej tudi

Osebna orodja