Машина Тьюринга - это интересно. Часть 1

Почему машина Тьюринга - это интересно?

1. Потому что машина Тьюринга - это краеугольный камень информатики и компьютерных наук.
2. Потому что она имеет отношение к криптовалютам (например, Ethereum построен на Тьюринг-полном языке программирования, а Bitcoin - нет).
3. Потому что она лежит в основе одной из так называемых "проблем тысячелетия" (Millenium Prize Problems) - математической задачи равенства классов P и NP, за решение которой можно получить миллион долларов (всего таких задач 7, одну из них - не связанную с машиной Тьюринга - решил Григорий Перельман, но отказался от этого миллиона)
4. Потому что рассуждения о машине Тьюринга приводят к интересным логическим и философским выводам.
5. Потому что я могу рассказать о ней на уровне, доступном и интересном для любого школьника (впрочем, школьники - более понятливый и любознательный народ, чем взрослые).
   Не буду говорить об Алане Тьюринге - человеке, который был кумиром для Стива Джобса: желающие могут почитать про него в интернете или посмотреть неплохой фильм "Игра в имитацию" с Камбербэтчем в главной роли. Буду говорить о самой машине Тьюринга.

Однако рассказ о машине Тьюринга будет простым и интересным, если рассказывать о ней постепенно, описывая ее по кусочкам. Поэтому пост имеет пометку "Часть 1". Если это окажется интересным для сообщества, то появятся части 2, 3, 4 и так далее. Рассказ был размещен мной также здесь

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

Другие кусочки являются такими же простыми, и из таких простых кусочков сложится машина Тьюринга - восхитительное изобретение, преобразившее наш мир.