Pierwsze trzynaście maszyn: T0: 00 → 00R, 01 → 00R, T1: 00 → 00R, 01 → 00L, T2: 00 → 00R, 01 → 01R, T3: 00 → 00R, 01 → 00STOP, T4: 00 → 00R, 01 → 10R, T5: 00 → 00R, 01 → 01L, T6: 00 → 00R, 01 → 00R, 10 → 00R, T7: 00 → 00R, 01 →???, T8: 00 → 00R, 01 → 100R, T9: 00 → 00R, 01 → 10L, T10: 00 → 00R, 01 → 11R, T11: 00 → 00R, 01 → 01STOP, T12: 00 → 00R, 01 → 00R, 10 → 00R
Większość jest niekompletna (bywa na przykład, że zawierają więcej, niż cztery jedynki z rzędu, czyli są niepoprawnie określone) lub nigdy się nie zatrzymuje, zdarzają się też powtórzenia. Żaden system kodowania nie pozwala wyeliminować wszystkich takich dat.
Pewna skomplikowana maszyna Turinga zastosowana do numeru dowolnej maszyny Turinga i jej argumentu da wynik działania tej maszyny.
Zobacz też automat Büchiego funkcja rekurencyjna maszyna RAM mrówka Langtona niedeterministyczna maszyna Turinga
Przypisy
Bibliografia
Linki zewnętrzne Polskojęzyczne Katarzyna Gawryś, Maszyna Turinga – podstawy działania i programowania, „Matematyka i Informatyka na Uczelniach Technicznych” (MINUT) – Politechnika Śląska, minut.polsl.pl, , 2023 [dostęp