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

Question

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

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

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

Answer 1

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