Как известно, определение того, останавливается ли машина Тьюринга, неразрешимо, но это не обязательно верно для более простых машин.

Foo машина представляет собой машину с конечной лентой, где каждая ячейка на ленте имеет целое число или символ HALT h, например ,

2 h 1 -1

Указатель инструкции начинается с указания на первую ячейку:

2 h 1 -1
^

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

-2 h 1 -1
     ^

Машина Foo продолжает делать это, пока указатель инструкции не укажет на символ остановки ( h). Итак, вот полное выполнение этой программы:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

Лента также является круглой, поэтому, если указатель инструкций перемещается с одной стороны ленты, он переходит на другую сторону, например:

3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

Одна интересная вещь об этих машинах Foo - то, что некоторые не останавливаются, например:

1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

Эта программа будет продолжаться в тех четырех последних состояниях навсегда.

Итак, напишите программу, которая определяет, останавливается ли машина Foo или нет! Вы можете использовать любой (разумный) формат ввода, который вам нравится для машин Foo, и вы можете использовать его 0в качестве символа остановки. Вы можете использовать любые два разных выхода для случая, когда он останавливается, и для случая, когда он не останавливается. Ваша программа, конечно, должна выводить ответ за ограниченное время для всех допустимых входных данных.

Это код-гольф , поэтому постарайтесь сделать свою программу максимально короткой!

Контрольные примеры

2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt

C # (интерактивный компилятор Visual C #) , 71 байт

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

Попробуйте онлайн!

Я не знаю, является ли следующее действительным, так как для него требуется пользовательский делегат с подписью unsafe delegate System.Action<int> D(int* a); и должен быть обернут в unsafeблок, который будет использоваться, но здесь это в любом случае:

C # (.NET Core) , 64 байта

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

Попробуйте онлайн!

Эта функция принимает int * и возвращает Action; другими словами, это функция карри. Единственная причина, по которой я использую указатели, заключается в codegolf.meta.stackexchange.com/a/13262/84206, который позволяет мне сохранять байты, уже имея переменную, уже определенную с длиной массива.

Сохранено 9 байтов благодаря @someone

Python 3 , 63 89 байт

def f(x):
 for i in range(2**len(x)):a=x[0];x[0]=-a;b=a%len(x);x=x[b:]+x[:b]
 return a==0

Попробуйте онлайн!

Также работает для Python 2; Байт можно сохранить в Python 2, заменив return на print и используя функцию print для stdout вместо return. R поворачивается Trueдля остановки и Falseне остановки.

Спасибо @Neil и @Arnauld за то, что я заметил, что мне нужно больше проверять, чтобы остановить. Спасибо @Jitse за указание на проблему с [2,0]. Спасибо @mypetlion за то, что отметили, что абсолютные значения ленты могут превышать длину ленты.

Желе , 15 11 байт

N1¦ṙ⁸ḢƊÐLḢẸ

Попробуйте онлайн!

Монадическая ссылка, которая принимает входные данные в виде списка целых чисел, используя 0 для обозначения остановки. Возвращает 0 для остановки ввода и 1 для тех, которые не останавливаются.

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

Спасибо @JonathanAllan за сохранение байта!

объяснение

      ƊÐL   | Loop the following as a monad until the result has been seen before:
N1¦         | - Negate the first element
   ṙ⁸       | - Rotate left by each of the elements
     Ḣ      | - Take just the result of rotating by the first element
         Ḣ  | Finally take the first element
          Ẹ | And check if non-zero

Python 3 , 91 байт

def f(a):
	s={0,};i=0
	while{(*a,)}-s:s|={(*a,)};a[i]*=-1;i-=a[i];i%=len(a)
	return a[i]==0

Попробуйте онлайн!

-40 байт благодаря Джокингу и Джитсе

Perl 6 , 46 43 36 байт

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]}

Попробуйте онлайн!

Представляет halt by 0и возвращает true, если машина останавливается. Это повторяет логические 2**(length n)времена, когда указатель попадает в ячейку остановки, в противном случае он остается в ячейке без остановки. Это работает, потому что существуют только 2**nвозможные состояния (игнорирование ячеек остановки) для машины Foo, так как каждая ячейка без остановки имеет только два состояния. Хорошо, да, есть состояния, чем это, но из-за ограниченных возможных переходов между указателями (и, следовательно, состояниями) будет менее 2 ** $ _ состояний ... Я думаю,

объяснение

{                                  }  # Anonymous codeblock
                     xx 2**$_         # Repeat 2**len(n) times
            .[0]*=-1                  # Negate the first element
 $_.=rotate(        )                 # Rotate the list by that value
                             ;!.[0]   # Return if the first element is 0

05AB1E , 14 13 байт

goFć©(š®._}®_

Попробуйте онлайн!

Принимает входные данные как список целых чисел с 0 в качестве инструкции остановки. Возвращает 1 для остановки и 0 для не остановки.

Спасибо @KevinCruijssen за сохранение 2 байта!

Java 8, 78 79 73 байта

a->{int k=0,l=a.length,i=0;for(;i++<1<<l;k%=l)k-=(a[k]*=-1)%l-l;k/=a[k];}

Прямой порт ответа @EmbodimentOfIgnorance 's C # .NET , так что не забудьте его поддержать!
Спасибо @Arnauld за нахождение двух ошибок (что также относится к некоторым другим ответам).

Приводит к java.lang.ArithmeticException: / by zeroошибке, когда она может остановиться, или нет, если нет.

Попробуйте онлайн.

Объяснение:

a->{                   // Method with integer-array as parameter and no return-type
  int k=0,             //  Index integer, starting at 0
      l=a.length,      //  The length `l` of the input-array
  i=0;for(;i++<1<<l;   //  Loop 2^length amount of times:
          k%=l)        //    After every iteration: take mod `l` of `k`
    k-=                //   Decrease `k` by:
       (a[k]*=-1)      //    Negate the value at index `k` first
                 %l    //    Then take modulo `l` of this
                   -l; //    And then subtract `l` from it
                       //  (NOTE: the modulo `l` and minus `l` are used for wrapping
                       //  and/or converting negative indices to positive ones
  k/=a[k];}            //  After the loop: divide `k` by the `k`'th value,
                       //  which will result in an division by 0 error if are halting

Haskell , 79 байтов

s x|m<-length x,let g(n:p)=(drop<>take)(mod n m)(-n:p)=iterate g x!!(2^m)!!0==0

Попробуйте онлайн!

Возвращает Trueза остановку машины и Falseпрочее. Ввод в виде списка с 0представлением состояния остановки.

Предполагается, что версия GHC больше 8,4 (выпущена в феврале 2018 года).

JavaScript (Node.js) , 71 67 байт

x=>{for(p=l=x.length,i=2**l;i--;)p+=l-(x[p%l]*=-1)%l;return!x[p%l]}

В основном так же, как @EmbodimentOfIgnorance 's C # .NET answer

4 байта сохраняются благодаря @Arnaud

Попробуйте онлайн!

JavaScript (Node.js) , 61 байт

x=>{for(p=l=x.length,i=2**l;i--;p+=l-(x[p%l]*=-1)%l)x[p%l].f}

Эта версия использует undefinedв качестве символа остановки и бросает a, TypeError: Cannot read property 'f' of undefinedкогда машина останавливается, и тихо завершает работу, когда машина не останавливается.

Попробуйте онлайн!

Scala , 156 байт

ИМО по-прежнему пригоден для игры в гольф, но пока я в порядке. Возвращает 0для не останавливающих Foos и 1для останавливающих Foos. Принимает входные данные в aвиде Array[Int], поэтому hпринимается как 0.

var u=Seq[Array[Int]]()//Keep track of all states
var i=0//Index
while(u.forall(_.deep!=a.deep)){if(a(i)==0)return 1//Check if we are in a previously encountered step ; Halt
u:+=a.clone//Add current state in the tracker
var k=i//Stock temp index
i=(a(i)+i)%a.length//Move index to next step
if(i<0)i+=a.length//Modulus operator in Scala can return a negative value...
a(k)*=(-1)}//Change sign of last seen index
0//Returns 0 if we met a previous step

Он довольно длинный для запуска (около 4 секунд для всех тестовых случаев) из-за нескольких выполненных мною поисков полного массива, а также для .deepсоздания копий ... Но вы все равно можете попробовать это онлайн.

Perl 5 -ap , 88 байт

for(;$F[$i]&&!$k{"$i|$F[$i]"};$i=($i+$F[$i])%@F){$k{"$i|$F[$i]"}=1;$F[$i]*=-1}$_=!$F[$i]

Попробуйте онлайн!

Атташе , 40 байт

Not@&N@Periodic[{On[0,`-,_]&Rotate!_@0}]

Попробуйте онлайн!

объяснение

{On[0,`-,_]&Rotate!_@0}

Это выполняет одну итерацию машины Foo; он отрицает первый член, затем вращает массив с помощью (исходного, неотрицанного) первого элемента массива.

Periodicбудет применять эту функцию, пока не будет получен повторяющийся результат. Машина либо останавливается, либо входит в тривиальный бесконечный цикл. Если он остановится, первый элемент будет 0. В противном случае он будет ненулевым.

&Nэто гольф-способ получения первого элемента числового массива. Затем Notвозвращается trueдля 0 (остановка машины) и falseдля всего остального (не остановка машины).

Древесный уголь , 28 байт

≔⁰ηＦＸ²Ｌ諧≔θ籧θη≧⁻§θη绬§θη

Попробуйте онлайн! Ссылка на подробную версию кода. Выходы, использующие логический выход Charcoal по умолчанию, который -для true и ничего для false. Объяснение:

≔⁰η

Инициализируйте указатель инструкции.

ＦＸ²Ｌθ«

Цикл столько раз, сколько есть теоретически возможных состояний.

§≔θ籧θη

Отмените значение в указателе инструкций.

≧⁻§θηη

Вычтите новое значение из указателя инструкций. Доступ к массиву угля является циклическим, поэтому он автоматически эмулирует кольцевую ленту Фу.

»¬§θη

В конце цикла выведите, остановилась ли программа.

Stax , 11 байт

Ç₧┬òE▐tµ|⌡1

Запустите и отладьте его

Он принимает входные данные в виде целочисленного массива с 0представлением остановки.

Это выводит 1для остановки и 0для машины без остановки.

Pyth , 12 байт

!hu.<+_hGtGh

Тестирование!

Использует прямой подход. Повторяйте, пока мы не увидим список дважды в одинаковом состоянии. Для программ, которые останавливаются, список в конечном итоге будет иметь лидерство, 0потому что именно там останавливается рекурсия. Для программ, которые не останавливаются, список не начинается с 0, а скорее находится в состоянии, из которого процесс будет периодическим, и поэтому машина Foo не будет останавливаться.