Задача о миниальной машине Тьюринга
Придумать самую простую машину Тьюринга, которая может земенить любую машину Тьюринга (если изначально найдет на ленте соответствующие инструкции).
Под простотой я имею ввиду малый алфавит и малое количество состояний.
P.S. http://en.wikipedia.org/wiki/Universal_Turing_machine#Smallest_machines
Это называется универсальная машина Тьюринга.
Самые простые имеют состояний и алфавит, соответственно,
(15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), (2, 18)
Под простотой я имею ввиду малый алфавит и малое количество состояний.
P.S. http://en.wikipedia.org/wiki/Universal_Turing_machine#Smallest_machines
Это называется универсальная машина Тьюринга.
Самые простые имеют состояний и алфавит, соответственно,
(15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), (2, 18)