Эквивалентность моделей вычислений

Я ищу объяснение того, как можно доказать, что модели вычислений эквивалентны. Я читал книги на эту тему, за исключением того, что доказательства эквивалентности опущены. У меня есть базовое представление о том, что означает эквивалентность двух моделей вычислений (представление автоматов: если они принимают одни и те же языки). Существуют ли другие способы думать об эквивалентности? Если бы вы могли помочь мне понять, как доказать, что модель машины Тьюринга эквивалентна лямбда-исчислению, этого было бы достаточно.


computation-theory lambda-calculus turing-machines
person mrk    schedule 13.08.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы доказать, что модель A эквивалентна модели B, вам нужно показать, что:

  1. Модель A не прочнее модели B
  2. Модель B не прочнее модели A

Чтобы показать, что модель X не сильнее модели Y, нужно доказать:

Для каждой машины из X существует машина из Y такая, что L(M_X) = L(M_Y)

[где M_X и M_Y — разные машины каждой модели соответственно]

Распространенными хорошо известными доказательствами являются:

Дополнительную информацию по этому вопросу можно прочитать в разделе эквиваленты машины Тьюринга.

Также обратите внимание, утверждение: the automata view: if they accept the same languages не соответствует действительности.
Вам не нужно показывать, что одни и те же автоматы принимают один и тот же язык в обеих моделях.
Необходимо показать, что для каждого автомата в A существует автомат в B такой, что L(M_A) = L(M_B) и наоборот

person amit    schedule 19.08.2012