FRACTRAN
FRACTRAN — повна за Тюрінгом езотерична мова програмування, яку запропонував Джон Конвей.
Опис
ред.Програма на FRACTRAN записується як упорядкований список додатних дробів разом з початковим початковим цілочисловим входом n. Програма запускається оновленням цілого числа n в такий спосіб:
- для першого дробу у списку, для якого добуток є цілим числом, замініть на
- повторюйте це правило доти, поки жоден дріб у списку не видасть цілого числа при множенні на , потім зупиніть.
Наприклад така програма генерує прості числа[ком. 1]:
Починаючи з n = 2, ця програма генерує таку послідовність цілих чисел:
- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … послідовність A007542 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
Після 2 ця послідовність містить такі степені 2:
- послідовність A034785 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
які є простими степенями 2.
Розуміння програми FRACTRAN
ред.Програма FRACTRAN може розглядатися як тип машини Мінського, де регістри зберігаються в простих показниках в аргументі n.
Використовувати нумерацію Геделя, додатне ціле число n може кодувати довільне число довільно великих додатних цілочислових змінних[ком. 2]. Значення кожної змінної кодується як показник простого числа в простій факторизації цілого числа. Наприклад, ціле число
представляє стан регістра, в якому одна змінна (яку ми будемо називати ) містить значення 2, а дві інші змінні ( і ) містять значення 1. Всі інші змінні містять значення 0.
Програма FRACTRAN — це впорядкований список додатних дробів. Кожен дріб є інструкцією, яка перевіряє одну або кілька змінних, представлених основними факторами її знаменника. Наприклад:
перевіряє дві змінні і . Якщо і , то виконуються присвоєння , , , . Наприклад:
Оскільки програма FRACTRAN є просто списком дробів, ці інструкції перевірка-присвоєння є єдиними допустимими інструкціями в мові FRACTRAN. Крім того, застосовуються такі обмеження:
- Кожного разу, коли виконується інструкція, змінні, що перевіряються, також зменшуються.
- Одну і ту ж змінну не можна одночасно зменшити і збільшити в одній інструкції (в іншому випадку дріб, що представляє цю інструкцію, не буде нескоротним).
- Інструкція FRACTRAN нездатна безпосередньо перевірити, чи дорівнює змінна 0. Однак є непрямий спосіб це зробити, створивши інструкцію, яка поміщається після інших інструкцій, які перевіряють конкретну змінну.
Коментарі
ред.- ↑ У Книзі чисел Джон Конвей і Річард Ґай дали трохи іншу послідовність:
- ↑ Нумерацію Геделя не можна безпосередньо застосувати для від'ємних цілих чисел, чисел з рухомою комою або текстових рядків, хоча можна домовитись щодо непрямого подання цих типів даних. Пропоновані розширення до FRACTRAN включають FRACTRAN++ [Архівовано 16 липня 2021 у Wayback Machine.] і Bag [Архівовано 16 липня 2021 у Wayback Machine.].
Примітки
ред.Посилання
ред.- «Prime Number Pathology: Fractran» [Архівовано 10 липня 2018 у Wayback Machine.]
- Weisstein, Eric W. FRACTRAN(англ.) на сайті Wolfram MathWorld.
- Prime Number Pathology [Архівовано 14 квітня 2013 у Archive.is]
- FRACTRAN [Архівовано 15 серпня 2021 у Wayback Machine.]
- Ruby implementation and example programs
- Project Euler Problem 308 [Архівовано 9 липня 2021 у Wayback Machine.]
- «Building Fizzbuzz in Fractran from the Bottom Up» [Архівовано 26 квітня 2017 у Wayback Machine.]
- Chris Lomont, «A Universal FRACTRAN Interpreter in FRACTRAN»