Unbeschränkte Sprachen lassen sich mit der Turing Machine (Turing Maschine) erkennen und überprüfen. Die TM unterliegt keiner Einschränkung bezüglich Speicherplatz oder Abarbeitung. Es handelt sich somit um eine Verallgemeinerung eines LBA (Linear Bounded Automaton), indem die Speicherbeschränkung aufgehoben wird. Jedes Feld des Bandes kann gelesen und verändert werden. Damit ist das Band vergleichbar mit dem Hauptspeicher eines modernen Rechners - mit dem Unterschied, dass Hauptspeicher von endlicher Grösse sind. Die TM ist praktisch nicht umsetzbar. Es handelt sich vielmehr um ein theoretisches Modell eines Rechners.

Eine TM besteht aus folgenden Komponenten:
Aus einer Kontrolleinheit mit einem Schreib-/ Lesekopf sowie einem einseitig unbegrenzten Band (Tape). Die Kontrolleinheit kann, wie beim FSA, endlich viele interne Zustände annehmen. Das Band dient zur Eingabe und Speicherung. Es ist in einzelne Felder unterteilt, die jeweils genau ein Zeichen aufnehmen können. Der Schreib-/ Lesekopf kann jeweils ein Feld lesen oder überschreiben. Das Band oder der Schreib-/ Lesekopf lassen sich um eine Position nach links oder rechts verschieben. Die TM wird folgendermassen dargestellt (nach [Stu95], S.185):
 

Formal wird die TM als 6-Tupel (S,I,B,S0,F,T) definiert, wobei
 S = endliche Menge von Zuständen (States)
 I = Eingabealpabet (input alphabet)
 B = Bandalphabet (tape alphabet)
 S0= Startzustand (Initial state)
 F = Endzustand (final state), wobei F Teil der Menge S ist
 T = Zustandsübergangsfunktion (transition function): Zustand x Bandsymbol x {L,R}
             -> (neuer) Zustand x (neues) Bandsymbol

 L und R bedeuten "gehe nach links", bzw. "gehe nach rechts"

Die TM unterscheidet zwischen dem Eingabealphabet und dem Bandalphabet. Das Eingabealphabet umfasst die Zeichen, die von "aussen" durch irgendeinen nicht näher spezifizierten Mechanismus auf das Band geschrieben werden können. Das Bandalphabet dagegen beinhaltet alle Zeichen, die die Maschine lesen und verarbeiten kann. Diese Menge umfasst neben dem Eingabealphabet in jedem Fall noch das Leersymbol *, welches einen leeren Feldinhalt anzeigt. (aus [Stu95], S.185). Da die TM einen Output generiert (=Resultat auf dem Speicherband), ist sie somit auch ein Transducer, ohne dass der Automat erweitert wird.