Читающие канал могли заметить, что мой фокус почти в 100% случаев направлен на практическую сторону вопроса, но это лишь часть картины. Во времена школы и бакалавриата всё было наоборот и я ценил лишь идейную составляющую, просто потом я, к счастью, потрогал траву.
Хоть жизнь и изменилась, интерес к некоторым вещам в математике у меня остался, и пока я ковырял квантовые компьютеры, меня и мои рекомендации в ютубе засосало в математический водоворот. Раз в ML в плане настоящего прогресса в последнее время тухло, я решил временно переключить фокус. Подсаживайтесь на пассажирское сидение.
Рассмотрим простейшую машину Тьюринга. У нас есть бесконечная лента из нулей и единиц и указатель на позицию на ленте. У машины есть N возможных состояний. Её программа задаётся таблицей, полностью описывающей её поведение. Для каждого текущего номера состояния и символа, на который смотрит указатель, указано 3 вещи:
1) Какой символ мы запишем в указанную позицию
2) Куда перемещаем указатель - на 1 клетку влево или вправо
3) В какое из состояний переключаемся, также можно полностью завершить программу.
В машину Тьюринга подают данные в виде символов на ленте, переключают указатель в стартовое состояние, и она делает шаги, пока не завершит программу. В теории она может и не завершиться, прям как ваше решение задачи на литкоде.
Несмотря на простоту, эта концепция сыграла огромную роль в истории развития Computer Science. Машина Тьюринга оказалось связующим звеном между всеми возможными способами представить классический алгоритм. Любая программа на любом языке программирования может быть представлена в виде той самой программы для машины Тьюринга.
И наоборот - если вы можете где-то реализовать машину Тьюринга, то можете реализовать и всё остальное. Рассмотрим мы это на моём любимом примере - майнкрафте. В нём существует редстоун - блок, который передаёт сигнал на соседний такой же блок. Игровая механика позволяет реализовать 2 логические операции -
NOT X и X OR Y. Их достаточно для создания продвинутых "микросхем", например, бинарного калькулятора, и примерно так я развлекался в школьные годы. Особо продвинутые ребята строили гораздо более мощные конструкции, вот тут, например, компьютер, на котором можно играть в змейку.
В майнкрафте можно сделать что угодно. В нём можно собрать компьютер, на котором можно играть в майнкрафт. В нём можно запустить ChatGPT и можно будет запустить искусственный суперинтеллект. Представьте ситуацию - злонамеренный ASI, который захватывает человечество изнутри компьютерной игры.
Почему это гарантированно возможно? Представленный набор логических блоков обладает достаточной мощностью, чтобы в Майнкрафте можно было собрать машину Тьюринга, что и сделали вот в этом или вот в этом видео, следовательно, возможно реализовать любое вычисление.
Для многих из вас всё это не является большим открытием - про машину Тьюринга часто рассказывают на первых курсах университета. Не беспокойтесь - это было всего лишь приведением к общему знаменателю для того, чтобы в следующий раз мы смогли погрузиться на экстремальные глубины того, что открывает нам этот концепт.
@knowledge_accumulator