Skip to main content
3 of 4
added 167 characters in body
user avatar
user avatar

TM and abstract algebra

Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Informal_description) and then their definition is formalized (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Formal_definition).

Is it possible to give another 'equivalent' definition that relies more precisely on algebraic concepts (i.e. algebraic structures: semigroups, monoids, etc; just like, for instance, regular languages are recognized by finite monoids and context-free languages are recognized by a product of a free group and a finite monoid)?

user60665