Как определить, что машина эквивалентна машине Тьюринга?

Question

Я нашел статью в Википедии список машинных эквивалентов Тьюринга . Однако в нем не описывается метод определения того, является ли данная машина эквивалентной машине Тьюринга.

Нужно ли мне использовать определение машины Тьюринга, чтобы доказать это? Не могли бы вы привести пример?

Спасибо.

Answer 1

Стандартный способ доказать что-то полное - это внедрить один из эквивалентов ТМ на вашем компьютере. Если это возможно, значит, ваша машина завершена. Если это не так, то это не так. Поэтому, если бы я пытался доказать, скажем, что новый язык программирования завершен, я выбрал бы TM-эквивалент, который проще всего реализовать, а затем показал бы, что мой язык программирования может имитировать его.

Answer 2

На самом деле это невозможно доказать. По крайней мере, для полной формализации этих общих доказательств равенства может потребоваться гораздо более формальная логика, чем можно ожидать даже в теоретической информатике. (если вы не согласны, скажите мне! Я готов обсудить это.)

Однако это в основном ясно из контекста. Вы пытаетесь построить симуляцию "машины" схемы вычисления A в другой такой модели вычисления B. Это означает, что B может моделировать A, и, следовательно, имеет полную мощность A. Если вы делаете наоборот, эти две модели называются эквивалент.

Answer 3

От всей души: если ваша машина может имитировать одну из известных машин, эквивалентных машине Тьюринга, то ваша машина также эквивалентна машине Тьюринга.

Возможно, самый простой способ сделать что-то подобное,

РЕДАКТИРОВАТЬ: Я не имею в виду, что это требование для машины, эквивалентной машине Тьюринга, хотя это может быть.Может быть, кто-то, кто немного более опытен в теоретической информатике, может прояснить мне это?