Univerzální Turingův stroj UTS má jak zpracovávaná data tak i tabulku řídícího konečného automatu KA umístěné na pásce Turingova stroje. Hlava neustále (až do ukončení činnosti algoritmu) přejíždí mezi záznamem tabulky a záznamem dat. Stavem UTS je nejen stav simulovaného Turingova stroje, ale i údaje potřebné pro přesun hlavy UTS na datové straně pásky, čtené a zapisované hodnotě a konečně o směru přechodu mezi tabulkou KA a záznamem dat. Pro takový rozšířený stav potřebujeme vytvořit tabulku UTS.