Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Представление машины Тьюринга совокупностью команд

• Совокупность всех команд, которые может выполнять машина, называется ее программой. Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты, программа, начальная конфигурация и указано, какие из символов обозначают пустую ячейку и заключительное состояние.
• Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:
• 1) начальному шагу алгоритма ставится в соответствие q 0 - начальное состояние;
• 2) циклы реализуются так, что последнее действие цикла должно соответствовать переходу в то состояние, которое соответствует началу цикла;
• 3) соседним шагам алгоритма соответствует переход в смежные состояния, которые соответствуют этим пунктам;
• 4) последний шаг алгоритма вызывает переход в заключительное состояние.

• В качестве примера рассмотрим совокупность команд машины Тьюринга, которая инвертирует входную цепочку, записанную с использованием нулей и единиц. Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, где символ ε соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q = {q0, q1, qz}. Если, например, начальная конфигурация имеет вид q0110011, то конечная конфигурация после завершения операции инвертирования должна иметь вид qz001100. Для решения задачи машиной будет порождена следующая совокупность команд: q01 → q00R, q10 → q10L, q00 → q01R, q11 → q11L, q0 ε → q1εL, q1ε → qzεR.