История изменений

МТ является лишь одной из возможных моделей вычислений. Другую популярную модель даёт лямбда-исчисление. Радость в том, что эти модели эквивалентны по отношению к понятию «вычислимости». Всё, что можно вычислить в одной модели, можно вычислить и в другой; и наоборот. Поэтому результаты по вычислимости, полученные для одной из этих моделей, автоматически распространяются на все остальные.

Кроме того, МТ принадлежит семейству эквивалентных друг другу, с точностью до полинома по времени и памяти, машин. Семейство примечательно тем, что в него входит RASP, которая чрезвычайно похожа на применяемые на практике компьютеры. МТ здесь дает удачный компромисс между наглядностью, удобством программирования и простотой формального описания: с помощью МТ удобно изучать проблемы, которые мы хотели бы решать на наших компьютерах. В результате мы знаем, что многие важные для народного хозяйства задачи лежат в злополучном NP; знаем о таких важных классах алгоритмов как монте-карло и лас-вегас (ZPP, RP, BPP).

МТ является лишь одной из возможных моделей вычислений. Другую популярную модель даёт лямбда-исчисление. Радость в том, что эти модели эквивалентны по отношению к понятию «вычислимости». Всё, что можно вычислить в одной модели, можно вычислить и в другой; и наоборот. Поэтому результаты по вычислимости, полученные для одной из этих моделей, автоматически распространяются на все остальные.

Кроме того, МТ принадлежит семейству эквивалентных друг к другу, с точностью до полинома по времени и памяти, машин. Семейство примечательно тем, что в него входит RASP, которая чрезвычайно похожа на применяемые на практике компьютеры. МТ здесь дает удачный компромисс между наглядностью, удобством программирования и простотой формального описания: с помощью МТ удобно изучать проблемы, которые мы хотели бы решать на наших компьютерах. В результате мы знаем, что многие важные для народного хозяйства задачи лежат в злополучном NP; знаем о таких важных классах алгоритмов как монте-карло и лас-вегас (ZPP, RP, BPP).