Почему ФРАКТРАН Тьюринг завершен?

10

Я попытался найти объяснение в Google, но большинство ссылок говорят только о таких вещах, как «FRACTRAN завершается. Как пример, давайте посмотрим на умножение».

Я помню, как видел на форуме xkcd сообщение о том, что FRACTRAN помог автору понять полноту Тьюринга. Я ищу интуитивно понятное объяснение того, почему этот esolang является полным по Тьюрингу, так как не очень очевидно смотреть на механику языка.

комар
источник
Для тех, кто не знаком с FRACTRAN: en.wikipedia.org/wiki/FRACTRAN
FrustratedWithFormsDesigner
2
Умножение причины - хороший пример полноты тьюринга, потому что оно требует и зацикливания, и хранения. Хотя это не полный тест, если что-то завершается. Лучшее «доказательство» - написать в нем эмулятор
мозгового штурма

Ответы:

12

Чтобы императивный язык был завершен по Тьюрингу, он должен иметь:

  1. Условный цикл
  2. Произвольное количество переменных

FRACTRAN - это язык, который состоит из ряда дробей, хранящих свои данные в показателях простых чисел.

Допустим, вы хотите добавить два числа: 2 a 3 b становится 5 ab

455 11 1 3 11 1
---, -, -, -, -, -
 33 13 11 7 2 3

Это программа FRACTRAN для внесения вышеуказанных изменений.

Вы начинаете с числа, такого как 72 (2 3 3 2 ). Программа идет «вперед», пока не найдет число, которое при умножении на инструкцию является другим целым числом (без остатка).

72побежит вперед, пока не доберется до 11/2. Затем он разделит число на 2и умножит его на 11(степень в 11 является переменной). Это дает 396. 396делится на 33 (уменьшая 3 степени и 11) и умножая на 455 (увеличивая 5, 7 и 13 переменных). И так далее. Полное описание этой программы и таблицу ее состояний можно прочитать на странице википедии FRACTRAN , включая действительно хороший анимированный GIF- файл вышеупомянутой программы.

Другие материалы FRACTRAN о Stack Exchange, которые касаются полноты Тьюринга, можно найти по адресу: Конвертировать Fractran в Brainfuck (хорошо, это действительно продуктивное использование своего времени)

Причина, по которой Fractran является Turing-complete, заключается в том, что он имитирует машину регистрации. Первичная факторизация числа хранит содержимое регистров, в то время как деление и умножение являются способом условного сложения и вычитания из регистров.

Часть хитрости здесь (и это начинает отклоняться от теории) заключается в том, что это закулисная машина регистрации Минского, для которой было доказано, что определенные ленты (программы) являются машинами Тьюринга, ЕСЛИ лента представлена ​​как число Геделя, которое точно, что такое номер FRACTRAN (со связанной страницы википедии):

Гедель использовал систему, основанную на простой факторизации. Сначала он назначил уникальное натуральное число каждому основному символу на официальном языке арифметики, с которым он имел дело.

Итак, у нас есть условные циклы, произвольные переменные, хранящиеся в виде чисел Гёделя, у нас есть машина Тьюринга.

Некоторое другое забавное чтение, которое затрагивает Collatz как природу FRACTRAN, можно прочитать в Can't Decide? Undecide! которые связывают гипотезу Коллатца с ФРАКТРАНОМ и проблему остановки.


FRACTRAN немного сложно разобраться.

Рассмотрим программу примерно так:

LABEL: start
    block1
    block2
    block3
    ...
END

При этом каждый блок имеет вид:

IF(registers X >= a, Y >= b)  # or any combination of registers
THEN
    X -= a
    Y -= b

    I += n
    J += m

    goto start

Первое утверждение из программы умножения выше:

455
---
 33

Будет написано в этой форме как:

IF(register `3` >= 1 && `11` >= 1)
THEN
     `3` -= 1
    `11` -= 1

     `5` += 1
     `7` += 1
    `13` += 1

    goto start

И, таким образом, вы можете ясно видеть хранилище данных и циклические конструкции, необходимые для полноты по Тьюрингу. Это очень элементарно, но он существует и работает как простой регистрационный компьютер - но это все, что вам действительно нужно сделать.


Все еще не убежден?

Это во многом заимствовано из лекции Дмитрия Хендрикса о моделях вычислений

Это берет очень простую программу, (2/3)которая является сумматором (2 a 3 b -> 3 a + b ), но это разрушительно - значение в 2 очищается как часть процесса.

Давайте напишем более высокий уровень FRACTRAN, который позволяет легко не делать такого разрушения.

Оригинальная программа может рассматриваться как:

   2
α: - → α
   3

В F 2 можно указать «функции» своего рода.

   10 1
α: - → α, - → β
    3 1

   3
β: - → β
   5 

Чтобы преобразовать программу F 2 (P) в стандартную программу FRACTRAN, необходимо:

  1. Очистить P от петель длины 1
  2. Замените греческие буквы (функции) свежими простыми числами
  3. Заменить переходы:
   туз
p: - → q, - → r, - -> s, ...
   BDF

будет выглядеть так:

водный курс
-, -, -, ...
бп дп фп

Для этого используются простые числа p, q, r и s для хранения состояния программы.

И затем у нас есть машина регистра ... у нее есть конечное число регистров, которые хранят произвольные большие числа и две инструкции:

  • inc (x i , m) - увеличить регистр i и перейти к строке m
  • jzdec (x i , m 1 , m 2 ) - если регистр i равен 0, перейти к строке m, иначе уменьшить i и перейти к строке m2.

Этот регистрационный компьютер был показан завершенным по Тьюрингу.

Затем он показывает процесс на нескольких слайдах компиляции машинной программы регистрации в программу FRACTRAN как часть механического процесса.

В принципе:

                       Пи)
inc (x (i), m) = ---- → m
                        1

                        1 1
jzdec (x (i), m1, m2) = ---- → m2, - → m1
                       р (я) 1

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

Кстати, если вы действительно хотите, чтобы ваш ум был взорван, прочитайте Code Golf: Fractran, в котором некоторые люди написали программу FRACTRAN для запуска другой программы FRACTRAN.

Сообщество
источник
2
И я подумал, что Brainf * ck был странным.
Роберт Харви
Обратите внимание, что системы векторного сложения связаны, так как любая программа Fractran может быть написана как VAS. А также сети Петри.
Дэн Д.