Причина, по которой машины Тьюринга важны при описании структур данных и алгоритмов, заключается в том, что они предоставляют математическую модель, в которой мы можем описать, что такое алгоритм. В большинстве случаев алгоритмы описываются с использованием языка высокого уровня или псевдокода. Например, я мог бы описать алгоритм для поиска максимального значения в массиве следующим образом:
Set max = -infinity
For each element in the array:
If that element is greater than max:
Set max equal to that element.
Из этого описания легко увидеть, как работает алгоритм, и было бы легко перевести его в исходный код. Однако предположим, что я написал это описание:
Guess the index at which the maximum element occurs.
Output the element at that position.
Это правильный алгоритм? То есть можно ли сказать «угадать индекс» и строго определить, что это значит? Если мы это допустим, сколько времени это займет? Если мы этого не допустим, почему бы и нет? Чем отличается первое описание от второго?
Чтобы получить математически строгое определение алгоритма, нам нужна некоторая формальная модель того, как компьютер работает и что он может и не может делать. Машина Тьюринга - это один из распространенных способов формального определения вычислений, хотя можно использовать и другие ( регистрирующие машины , системы переписывания строк, лямбда-исчисление Черча и т. Д.) мы определили математическую модель вычислений, мы можем начать говорить о том, какие виды алгоритмических описаний являются действительными, а именно те, которые могут быть реализованы с использованием нашей модели вычислений.
Многие современные алгоритмы критически зависят от свойств базовой модели вычислений. Например, алгоритмы кеширования предполагают, что модель вычислений имеет некоторый буфер памяти неизвестного размера и двухуровневую память. Некоторые алгоритмы требуют, чтобы базовый компьютер был транскдиотомным , что означает, что размер машинного слова должен быть по крайней мере достаточно большим, чтобы вместить размер любой проблемы. Рандомизированные алгоритмы требуют формального определения случайного числа и того, как машина может использовать случайные значения. Недетерминированные алгоритмы требуют средств для определения недетерминированных вычислений. Алгоритмы, основанные на схемах, должны знать, что такое схемные примитивы и не допускаются. Квантовые компьютеры нуждаются в формальном определении того, какие операции разрешены и запрещены, а также в определении алгоритма, что выходные данные являются вероятностными. Распределенные алгоритмы требуют формального определения связи между машинами.
Короче говоря, важно четко указывать, что разрешено и запрещено при описании алгоритма. Однако, чтобы быть хорошим программистом или иметь четкое представление о алгоритмах, вам не нужно обязательно знать машины Тьюринга изнутри и снаружи, а также вам не нужно знать о конкретных деталях того, как вы будете кодировать конкретные проблемы, используя их , Однако вы должны знать, что модель вычислений может и не может делать, и какова стоимость каждой операции. Таким образом, вы можете рассуждать о том, насколько эффективны алгоритмы, сколько различных ресурсов (время, пространство, память, общение, случайность, недетерминизм и т. Д.) Они используют. Но, тем не менее, не паникуйте, если вы не понимаете основную модель.
Есть еще одна причина подумать о базовой модели вычислений - обсудить ее ограничения. У каждой модели вычислений есть свои пределы, и в некоторых случаях вы можете доказать, что определенные алгоритмы не могут существовать для определенных задач или что любой алгоритм, который решит какую-то проблему, обязательно должен использовать некоторое количество заданного ресурса. Наиболее распространенный пример, когда это возникает в алгоритме проектирования, это понятие NP-твердости. Предполагается, что некоторые проблемы чрезвычайно «трудно» решить, но формальные определения того, что это за сложность, основаны на знании машин Тьюринга и недетерминированных машин Тьюринга. Понимание модели полезно в этом случае, потому что она позволяет рассуждать о вычислительной выполнимости определенных проблем.
Надеюсь, это поможет!