Revista Română de Informatică și Automatică / Vol. 4, Nr. 2-3, 1994

TMS. Limbaj de specificare pentru maşini Turing

Silviu CALINOIU

Rezumat:

Maşinile Turing au fost imaginate din nevoia de a formaliza conceptul de algoritm. Deşi definiția lor este foarte “puternică” (în sensul definirii frontierei între calculabil şi necalculabil), din punct de vedere al expresivităţii definiţia este greu de folosit. De aceea, matematicienii au introdus noțiunea de maşină Turing compusă specificată prin intermediul unui graf ce conține în noduri maşini Turing. Limbajul prezentat în articolul de faţă oferă ambele posibilități de specificare, maşini simple şi compuse. Totodată, datorită creşterii expresivităţii se oferă posibilitatea punerii în discuţie a unor analogii interesante cu limbajele de programare clasice, cum ar fi: abstractizare procedurală, recursivitate, flux de control ş.a.m.d.

Cuvinte cheie:
mașini Turing, mașini elementare, compunere de maşini, conceptul de variabilă.

Vizualizează articolul complet:

CITAREA ACESTUI ARTICOL SUNT URMĂTOARELE:
Silviu CALINOIU, „TMS. Limbaj de specificare pentru maşini Turing”, Revista Română de Informatică și Automatică, ISSN 1220-1758, vol. 4(2-3), pp. 49-54, 1994.