Уважаемые пользователи Голос!
Сайт доступен в режиме «чтение» до сентября 2020 года. Операции с токенами Golos, Cyber можно проводить, используя альтернативные клиенты или через эксплорер Cyberway. Подробности здесь: https://golos.io/@goloscore/operacii-s-tokenami-golos-cyber-1594822432061
С уважением, команда “Голос”
GOLOS
RU
EN
UA
artishok
7 лет назад

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

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

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

Не буду говорить об Алане Тьюринге - человеке, который был кумиром для Стива Джобса: желающие могут почитать про него в интернете или посмотреть неплохой фильм "Игра в имитацию" с Камбербэтчем в главной роли. Буду говорить о самой машине Тьюринга.

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

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

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

1
0.014 GOLOS
На Golos с December 2017
Комментарии (11)
Сортировать по:
Сначала старые