Andrej Bauer: Kako primerjamo programske jezike

Povzetek: Znano je, da so mnogi računski modeli (Turingovi stroji, splošne rekurzivne funkcije, λ-račun) med seboj Turingovo ekvivalentni, kar pomeni, da vsi računajo isti razred številskih funkcij, ki jim pravimo izračunljive delne funkcije. Ta mera ekvivalentnosti pa ni ustrezna za primerjavo izrazne moči programskih jezikov: čeprav lahko v strojni kodi izračunamo natanko vse tisto, kar lahko izrazimo v višjem programskem jeziku, to ne pomeni, da sta jezika ekvivalentna za uporabo. Ogledali si bomo splošno teorijo računskih modelov in ustrezno definicijo morfizmov med njimi, s katero lahko primerjamo izrazno moč programskih jezikov. Kakšnih zanimivih izrekov pa ne bomo dokazali, ker jih zaenkrat ni.

Vabljeni!