Насколько произвольным является представление машины Тьюринга?

Question

Я работаю над связанной разрешающей/распознаваемой проблемой, и для ее решения мне нужно уточнить кодирование/представление машины для turing.

Я знаю, что машина для turing формально определена как 7-кортеж. Если у меня есть машина Тьюринга U и еще одна машина Тьюринга M, тривиально спроектировать U, чтобы распознать часть M (например, алфавит M, символы ввода, набор принимающих состояний и т. Д.)?

Часть меня думает, что, поскольку это конечные множества, тривиально считать их, но часть меня задается вопросом, можете ли вы просто перечислить часть определения M без возможности зацикливания на бесконечность.

Answer 1

Да, U обозначает универсальную машину Тьюринга. Читайте об этом на http://en.wikipedia.org/wiki/Turing_machine#Universal_Turing_machines.