Что вычислила таинственная маленькая программа Тьюринга на компьютере в Манчестере?

10

Я читаю газету Тьюринга «Вычислительная техника и интеллект» ( https://www.csee.umbc.edu/courses/471/papers/turing.pdf ) и нашел фрагмент, в котором он говорит:

Я установил на компьютере Манчестера небольшую программу, использующую только 1000 единиц хранения, в результате чего машина, снабженная одним шестнадцатизначным числом, отвечает другой в течение двух секунд. Я бы никому не понравился, чтобы узнать из этих ответов достаточно о программе, чтобы можно было предсказать любые ответы на непроверенные значения.

Для меня это похоже на проблему машинного обучения :), но если оставить в стороне мой интерес к искусственному интеллекту, мой вопрос заключается в следующем:

Кто-нибудь знает, что делала эта программа?

Мне очень любопытно.

PS: по длине ввода и вывода, я подозреваю, что это был алгоритм шифрования, но я был бы признателен за любую подсказку к реальной программе.

Нанаки
источник

Ответы:

2

Вы правы, что это связано с шифрованием, но это не шифрование как таковое. Это то, что называется хешированием. Что его программа делает, так это берет число, хэширует его и выводит хеш. То, что создал Тьюринг, теперь называется криптографически безопасным хэшем.

Современный криптографически безопасный хеш должен делать следующее. Должно быть легко хэшировать входные данные, но очень трудно «хэшировать» выходные данные, чтобы получить входные данные. В этом случае «очень сложно» обычно означает «на суперкомпьютере потребуются месяцы или годы, если не больше».

Х. Антонио Перес
источник
Обычно мы думаем, что хеш имеет неограниченную область, тогда как в этом случае область и диапазон одинаковы. В этом смысле это больше похоже на одностороннюю функцию. Тем не менее, и хеш, и односторонняя функция на самом деле легко вычисляются, тогда как здесь дело в том, что она выглядит случайной, как псевдослучайная функция.
Юваль
2
Спасибо @JorgePerez! Я знаю, что такое хеш, мой вопрос был больше похож: какой хеш он реализовал? Есть ли какие-нибудь заметки по этому поводу? Может быть, он опубликовал алгоритм? Извините, если мне не ясно :)
Нанаки
2
У вас есть ссылка, которую вы можете привести?
Рафаэль