Войти  |  Регистрация
Авторизация
» » FRACTRAN

FRACTRAN



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

Описание

Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом n. Программа запускается путём обновления целого числа n следующим образом:

  • для первой дроби f {displaystyle f} в списке, для которой произведение n ⋅ f {displaystyle ncdot f} является целым числом, замените n {displaystyle n} на n ⋅ f {displaystyle ncdot f}
  • повторяйте это правило до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на n {displaystyle n} , затем остановите.
  • Например следующая программа генерирует простые числа:

    ( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 2 , 1 7 , 55 1 ) {displaystyle left({frac {17}{91}},{frac {78}{85}},{frac {19}{51}},{frac {23}{38}},{frac {29}{33}},{frac {77}{29}},{frac {95}{23}},{frac {77}{19}},{frac {1}{17}},{frac {11}{13}},{frac {13}{11}},{frac {15}{2}},{frac {1}{7}},{frac {55}{1}} ight)}

    Начиная с n = 2, эта программа генерирует следующую последовательность целых чисел:

    2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... последовательность A007542 в OEIS

    После 2 эта последовательность содержит следующие степени 2:

    2 2 = 4 , 2 3 = 8 , 2 5 = 32 , 2 7 = 128 , 2 11 = 2048 , 2 13 = 8192 , 2 17 = 131072 , 2 19 = 524288 , … {displaystyle 2^{2}=4,,2^{3}=8,,2^{5}=32,,2^{7}=128,,2^{11}=2048,,2^{13}=8192,,2^{17}=131072,,2^{19}=524288,,dots } последовательность A034785 в OEIS

    которые являются простыми степенями 2.

    Понимание программы FRACTRAN

    Программа FRACTRAN может рассматриваться как тип машины Минского, где регистры хранятся в простых показателях в аргументе n.

    Используя нумерацию Гёделя, положительное целое число n может кодировать произвольное число произвольно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель простого числа в простой факторизации целого числа. Например, целое число

    60 = 2 2 × 3 1 × 5 1 {displaystyle 60=2^{2} imes 3^{1} imes 5^{1}}

    представляет состояние регистра, в котором одна переменная (которую мы будем называть v 2 {displaystyle v_{2}} ) содержит значение 2, а две другие переменные ( v 3 {displaystyle v_{3}} и v 5 {displaystyle v_{5}} ) содержат значение 1. Все остальные переменные содержат значение 0.

    Программа FRACTRAN — это упорядоченный список положительных дробей. Каждая дробь представляет собой инструкцию, которая проверяет одну или несколько переменных, представленных основными факторами её знаменателя. Например:

    f 1 = 21 20 = 3 × 7 2 2 × 5 1 {displaystyle f_{1}={frac {21}{20}}={frac {3 imes 7}{2^{2} imes 5^{1}}}}

    проверяет две переменные v 2 {displaystyle v_{2}} и v 5 {displaystyle v_{5}} . Если v 2 ≥ 2 {displaystyle v_{2}geq 2} и v 5 ≥ 1 {displaystyle v_{5}geq 1} , то выполняются присвоения v 2 := v 2 − 2 {displaystyle v_{2}:=v_{2}-2} , v 5 := v 5 − 1 {displaystyle v_{5}:=v_{5}-1} , v 3 := v 3 + 1 {displaystyle v_{3}:=v_{3}+1} , v 7 := v 7 + 1 {displaystyle v_{7}:=v_{7}+1} . Например:

    60 ⋅ f 1 = 2 2 × 3 1 × 5 1 ⋅ 3 × 7 2 2 × 5 1 = 3 2 × 7 1 {displaystyle 60cdot f_{1}=2^{2} imes 3^{1} imes 5^{1}cdot {frac {3 imes 7}{2^{2} imes 5^{1}}}=3^{2} imes 7^{1}}

    Поскольку программа FRACTRAN представляет собой просто список дробей, эти инструкции проверка-присвоение являются единственными допустимыми инструкциями на языке FRACTRAN. Кроме того, применяются следующие ограничения:

    • Каждый раз, когда выполняется инструкция, проверяемые переменные также уменьшаются.
    • Одна и та же переменная не может быть одновременно уменьшена и увеличена в одной инструкции (в противном случае дробь, представляющая эту инструкцию, не будет несократимой).
    • Инструкция FRACTRAN неспособна непосредственно проверить, равна ли переменная 0. Однако есть непрямой способ это сделать путём создания инструкции, которая помещается после других инструкций, которые проверяют конкретную переменную.

    Добавлено Admin 22-07-2022, 20:00 Просмотров: 15
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent