Тьюринг завершен

Turing Complete относится к машине, которая при наличии достаточного количества времени и памяти вместе с необходимыми инструкциями может решить любую вычислительную задачу, какой бы сложной она ни была. Этот термин обычно используется для описания современных языков программирования, поскольку большинство из них являются полными по Тьюрингу (C++, Python, JavaScript и т. д.).

Что такое машина Тьюринга?

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

Алан представлял свою машину как длинный кусок ленты с записанной на нем информацией в виде двоичного кода (1 и 0). Машина также будет иметь головку чтения/записи, которая перемещается по ленте и считывает каждый квадрат один за другим. Код задавал машине вычислительную задачу, а длина ленты была такой, какая была необходима для решения.

Когда головка движется по ленте, машина следует простым инструкциям, определяющим ее реакцию. Он читает ленту, следует инструкциям и выполняет определенные действия для записи нового кода по мере продвижения. Этот новый шаблон кода является ответом на проблему. Гипотетическая машина Тьюринга могла решить любую вычислительную задачу, которую можно было выразить в коде (и которая имела вычисляемый ответ).

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

Простой калькулятор является примером системы, которая является неполной по Тьюрингу, поскольку она может выполнять только несколько типов вычислений. Напротив, программируемый научный калькулятор (способный выполнять все виды вычислений) можно рассматривать как машину Тьюринга.

Блокчейн и полнота по Тьюрингу

В то время как некоторые приложения технологии блокчейна являются завершенными по Тьюрингу, другие — неполными по Тьюрингу. Это зависит от реализованной технологии сценариев. Например, язык сценариев, используемый в биткойнах, намеренно разработан как неполный по Тьюрингу, потому что он служит своей цели, а повышенная сложность потенциально может вызвать проблемы. Сохраняя его простым, разработчики могут с высокой точностью предсказать, как он будет реагировать в конечном числе ситуаций, в которых он используется.

Ethereum, с другой стороны, построен как блокчейн Turing Complete. Это важно, потому что необходимо понимать соглашения, из которых состоят смарт-контракты. Будучи завершенным по Тьюрингу, Эфириум способен понимать и реализовывать любые будущие соглашения, даже те, о которых еще не думали. Другими словами, полнота Тьюринга Ethereum означает, что он может использовать свою кодовую базу для выполнения практически любой задачи, если у него есть правильные инструкции, достаточно времени и вычислительной мощности.