Блог

Теперь перейдем к самому интересному вопросу: для чего же нужны машины Тьюринга? Как и где их использовать? Главное, что умеют машины Тьюринга - это осуществлять любые вычисления, какими сложными они бы ни были (есть некоторые суперспецифические исключения из этого правила, но о них пока не…

В Части 1 я начал рассказ про то, почему машина Тьюринга - это интересно, и про то, что такое лента машины Тьюринга (бесконечная строка из клеток, в каждой из которых написаны 0 или 1). В этой части я завершу описание машины Тьюринга и предложу на выбор читателям несколько вариантов того, про что мне писать дальше. Вначале расскажу о следующей важной детали: считывающей головке. Представьте, что вы поставили карандашик напротив какой-нибудь клеточки с числом, а потом взяли и сдвинули этот карандашик на одну клеточку, например, вправо.

Почему машина Тьюринга - это интересно? Потому что машина Тьюринга - это краеугольный камень информатики и компьютерных наук. Потому что она имеет отношение к криптовалютам (например, Ethereum построен на Тьюринг-полном языке программирования, а Bitcoin - нет). Потому что она лежит в основе одной из так называемых "проблем тысячелетия" (Millenium Prize Problems) - математической задачи равенства классов P и NP, за решение которой можно получить миллион долларов (всего таких задач 7, одну из них - не связанную с машиной Тьюринга - решил Григорий Перельман, но отказался от этого миллиона)…