Laskennan malli
 |
Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan. |
Laskennan malli on tietokoneen tai ohjelmointikielen matemaattinen malli ja siten formaali perusta algoritmeille.
Tunnetuimmat laskennan mallit ovat kaksi historiallisesti ensimmäistä. Alan Turing julkaisi Turingin koneen, tietokoneen matemaattisen mallin, vuonna 1936. Samaan aikaan Alonzo Church kehitti lambda-kalkyylin, jota nykyään pidetään funktio-ohjelmointikielen matemaattisena mallina. Myöhemmin mallien huomattiin olevan ekvivalentit eli niille kirjoitetut ohjelmat voidaan kääntää toisikseen. Turingin kone ja sen kanssa ekvivalentit eli Turing-täydelliset mallit voivat laskea kaikki ne ongelmat, joita ylipäätään osataan laskea.
Myös Turingin konetta heikompia laskennan malleja käytetään. Äärellinen automaatti eli tilakone on yksinkertaisen tilasta toiseen siirtyvän koneen malli. Sillä on ekvivalenssisuhde säännöllisten kielten kanssa. Malliin ei sisälly muistia, joten sitä voidaan käyttää hyväksi silloin, kun muisti on rajallinen.