Každý Turingův stroj můžeme zakódovat do jednoho řetězce. Existuje nekonečně mnoho způsobů, jak TS zakódovat, záleží na vlastní definici. Můžeme například očíslovat všechny stavy, očíslovat všechny symboly z abecedy a očíslovat všechny směry, kterými se může čtecí hlava vydat. Následně můžeme přechodovou funkci (q<sub>1</sub>,a<sub>2</sub>)→(q<sub>3</sub>,t<sub>6</sub>,L<sub>1</sub>), kde dolní idnexyindexy označují očíslování, zakódovat takto: <code>01001000100000010</code>. Jako oddělovač jsme použili jedničku a počet nul se vždy rovná očíslování daného objektu. Více různých přechodových funkcí můžeme oddělit dvěma jedničkami, takže pokud bychom přidali ještě funkci (q<sub>1</sub>,b<sub>3</sub>)→(q<sub>3</sub>,t<sub>6</sub>,R<sub>2</sub>), získali bychom řetězec <code>01001000100000010110100010001000000100</code>. Takto můžeme zakódovat všechny přechodové funkce. Zbývá už jen označit startovací, přijímající a ukončovací stav, což můžeme udělat například tak, že startovací stav bude mít vždy index jedna, přijímající dva a zamítající tři. Do tohoto formátu pak můžeme zakódovat libovolný TS. Důsledkem tohoto faktu je, že množina všech Turingových strojů je [[Spočetná množina|spočetná]].
