Это следствие полноты Тьюринга , которое было установлено много десятилетий назад.
Алан Тьюринг, известный ученый, доказал, что любая вычисляемая функция может быть вычислена с использованием машины Тьюринга . Машина Тьюринга - это очень простое теоретическое устройство, которое может делать только несколько вещей. Он может читать и записывать на ленту (т. Е. В память), поддерживать внутреннее состояние, которое изменяется содержимым, считываемым из памяти, и использовать внутреннее состояние и последнюю ячейку памяти для чтения, чтобы определить, в каком направлении перемещать ленту перед чтением следующего ячейка памяти.
Операции присваивания, условия и цикла достаточны для моделирования машины Тьюринга. Чтение и запись памяти и поддержание состояния требует назначения. Изменение направления ленты в зависимости от состояния и содержимого памяти требует условных циклов и циклов. «Петли» на самом деле немного более высокого уровня, чем на самом деле требуется. Все, что действительно требуется, - это то, что поток программы может как-то прыгнуть назад. Это подразумевает, что вы можете создавать циклы, если хотите, но язык не должен иметь явную конструкцию цикла.
Поскольку эти три операции позволяют моделировать машину Тьюринга, и было доказано, что машина Тьюринга способна вычислять любую вычислимую функцию, из этого следует, что любой язык, обеспечивающий эти операции, также способен вычислять любую вычислимую функцию.
Редактировать: И, как указывали другие ответчики, эти операции не должны быть дискретными. Вы можете создать одну инструкцию, которая выполняет все эти три вещи (назначать, сравнивать и разветвлять) таким образом, чтобы она сама могла имитировать машину Тьюринга.