Основы компьютерных наук: Машины Тьюринга и полнота Тьюринга.
Хотите узнать, на сколько мощным является Ethereum на самом деле?
Вам необходимо понять эту ключевую концепцию!
Изобретенная Аланом Тьюрингом в 1930-х годах, который назвал ее "а-машиной", машина Тьюринга представляет собой (абстрактную) модель вычислений.
Концепция построена на простой гипотетической машине. Она содержит 3 ключевых компонента:
- Лента, представляющая собой память
- Головка, отслеживающая положение машины
- Инструкции, указывающие машине, как обрабатывать данные.
Инструкция - это набор условий и связанных с ними операций.
Существует 3 возможных операции:
- Считать символ под головкой
- Редактировать (записать и/или стереть) символ под головкой
- Переместить влево или вправо на одну клетку
Машина Тьюринга может выглядеть следующим образом. Хотя мы будем придерживаться 0 и 1, машина Тьюринга может обрабатывать любые буквы, цифры или символы.
Далее, давайте создадим инструкцию.
Наша цель - поменять 1 на 0 и наоборот.
Шаг 1 - Прочитайте запись и определите, что это - 1 или 0.
Шаг 2 - Запишите новый символ
Шаг 3 - Перейдите к следующему числу
Поздравляем! Мы создали нашу первую инструкцию.
Если мы выполним нашу инструкцию еще два раза, то окажемся на пустом месте. Наша машина Тьюринга будет следовать нашей инструкции и ждать бесконечно.
На этом этапе мы должны ввести последнее понятие, необходимое для машины Тьюринга: состояние машины.
Теперь, когда машина Тьюринга может понимать состояние, она может принимать решения, основываясь на контексте данных на ленте.
В этом примере мы ввели состояние, которое предписывает машине остановиться, но мы можем использовать эту концепцию, чтобы начать реализовывать более сложные функции.
Рассмотрим этот набор инструкций машины Тьюринга.
В состоянии 0 головка движется вправо, инвертируя каждый символ. Когда она достигнет пустого пространства, то перейдет в состояние 1.
В состоянии 1 головка перемещается вправо и снова инвертирует символы. При достижении пустого места программа завершается.
На этом наш пример заканчивается, что немного глупо. Все, что он делает, это инвертирует число туда и обратно, заканчивая исходным состоянием.
Введя в нашу программу больше состояний, мы можем поручить машине Тьюринга выполнение более сложных функций.
На самом деле, при достаточном количестве состояний и достаточно подробном наборе инструкций машина Тьюринга способна выполнить ЛЮБОЕ вычисление, на которое способен современный компьютер.
Взгляните на свой Macbook. Если вы можете сделать что-то на этом компьютере, то (теоретически) вы можете сделать это и на машине Тьюринга.
В теории вычислимости Тьюринг-полнота - это обозначение, которое описывает систему с формальными и конкретными требованиями. Пока что мы будем придерживаться высокого уровня.
Давайте воспользуемся следующим определением: система является Тьюринг-полной, если она может моделировать машину Тьюринга.
За последнее столетие Тьюринг, Чёрч и гиганты, которые развили их работу, математически доказали, что если вы можете смоделировать машину Тьюринга на вычислительной системе, вы также можете смоделировать эту систему на машине Тьюринга.
Проще говоря, если система является Тьюринг-полной, то она способна на все, что может сделать любая другая Тьюринг-полная система.
Вот две части информации:
- большинство современных языков программирования являются Тьюринг-полными
- Solidity является Тьюринг-полной
Тьюринг-полнота позволяет нам с математической уверенностью сказать, что
Ethereum способен на все, что может сделать ваш компьютер.
Ethereum - это всемирный компьютер, криптовалюта - программируемые деньги, De-Fi - это возможно...
Потому что Solidity - это Тьюринг-полнота!
Мы всё еще рано. Настолько рано, что легко пропустить то, что происходит.
Но пропустить происходящее было бы трагедией, потому что в криптовалюте происходит нечто особенное.
Рождается новый тип компьютера.
По мере того как мы углубляемся в 2020-е годы, я с сожалением констатирую, что мир становится все мрачнее и мрачнее.
Макроэкономика рушится, старые методы работы терпят крах, ресурсы не доступны там, где они необходимы.
Нам нужно найти новый способ координации.
Когда я смотрю в будущее, я вижу много причин для страха. Но как бы мрачно не было, я все равно каждый день просыпаюсь и с радостью вхожу в систему.
С нетерпением жду начала строительства.
Вы большие молодцы, если дочитали до конца! (даже если мало что поняли)
Ethereum : Всемирный Компьютер, часть 1
Пишите если есть ошибки в переводе