Romanian Journal of Information Technology and Automatic Control / Vol. 4, No. 2-3, 1994

TMS. Specification Language for Turing Machines

Silviu CALINOIU

Abstract:

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.

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

View full article:

CITE THIS PAPER AS:
Silviu CALINOIU, "TMS. Specification Language for Turing Machines", Romanian Journal of Information Technology and Automatic Control, ISSN 1220-1758, vol. 4(2-3), pp. 49-54, 1994.