태그 보관물: halting-problem

halting-problem

Befinge의 정지 문제 해결 도달하면 프로그램이 중지됩니다. 모든 Befinge 프로그램은 분명히

간단한 2D 언어를 정의 해 봅시다 . 엄청나게 독창적 인 이름 인 befinge를 드리겠습니다 . Befinge에는 5 가지 지침이 있습니다.

  • <>^v대부분의 2D esolang에서와 같이 명령 포인터를 해당 방향으로 리디렉션합니다.
  • . no-op입니다.

명령 포인터는 오른쪽 상단에서 시작합니다. 명령 포인터가 가장자리에 도달하면 프로그램이 중지됩니다. 모든 Befinge 프로그램은 분명히 아무 것도하지 않는 무한 루프로 정지하거나 들어갑니다. 다음은 두 가지 예입니다.

정지 :

>.v
..<

비 경고 :

>....v
..v..<
..>v..
^..<..

중단 문제는 Turing-complete 언어에서는 해결할 수 없지만이 문제에 해당됩니다. 당신의 임무는 befinge 프로그램을 나타내는 문자열을 입력으로 받아 중단 여부에 따라 참 또는 거짓 값을 반환 하는 프로그램 (또는 함수)을 작성하는 것입니다.

  • 입력은 이러한 문자로만 구성되고 사각형으로 구성되는 공백으로 채워질 것이라고 가정 할 수 있습니다.
  • 지침에 5 자 세트를 사용할 수 있습니다 (예 🙂 adws .

테스트 사례

정지 :

.


v>
>^


....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.


v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<

비 경고 :

>..v
^..<


>v<
v<.
>v.
v<.
>.^


>.>.>.v
.><.<.<

이것은 code-golf 이므로 가장 짧은 프로그램 (바이트)이 이깁니다.

답변

ES6 (자바 스크립트) 111, 101 바이트

편집 : Y 및 N 대신 출력 값을 true 및 false 로 변경했습니다 . 하여 10 바이트를 더 줄

골프

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

테스트

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
`>.v
..<`
,'Y');

//Non-Halting
T(
`>....v
..v..<
..>v..
^..<..`
,'N');

//Halting
T(
`.`
,'Y')

//Halting
T(
`v>
>^`
,'Y');

//Halting
T(
`....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.`
,'Y');

//Halting
T(
`v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<`
,'Y');

//Non-Halting
T(
`>..v
^..<`
,'N');

//Non-Halting
T(
`>v<
v<.
>v.
v<.
>.^`
,'N');

//Non-Halting
T(
`>.>.>.v
.><.<.<`
,'N');

샘플 출력

#Halting
I=
>.v
..<
F(I)= true
OK !

#Non-Halting
I=
>....v
..v..<
..>v..
^..<..
F(I)= false
OK !

#Halting
I=
 .
F(I)= true
OK !

#Halting
I=
v>
>^
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<
F(I)= true
OK !

#Non-Halting
I=
>..v
^..<
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.<
F(I)= false
OK !

답변

파이썬 2 , 116 105 바이트

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y

온라인으로 사용해보십시오!

도전은 오래되었지만 이것이 가장 짧은 파이썬이므로 게시 할 것이라고 생각했습니다. 입력은 문자열 목록이지만 사용 된 문자는 일반적이지 않습니다.

> G
< B
v C
^ F
. L

예를 들어, 세 번째 중지 예제는로 바뀝니다 ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. 출력은 종료 코드를 통해 이루어지며 정지하지 않을 경우 0 (성공), 정지 할 경우 1 (오류)입니다. 모든 팁이나 트릭에 감사드립니다.

답변

비 펀지-98 (PyFunge) , 217 (209) 200 바이트

#v10dpf1dp12dp3dpk
 >#v~:a-#v_$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
  <   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_

온라인으로 사용해보십시오!

befinge 중지 문제에는 befunge 솔루션이 필요합니다. truey이면 0을, falsey이면 1을 반환합니다. 1,15부터 시작하여 그리드에 입력을 놓은 다음 위쪽으로 이동하여 화살표를 0으로 바꿉니다. 우리가 0에 도달하자마자 우리는 그것이 반복되는 것을 알고 있습니다. > <^ v 이외의 모든 것. 0은 프로그램을 정지시키는 것으로 간주됩니다. 여기에는 프로그램을 그리드에 약간 오프셋하여 배치하는 공간의 경계가 포함됩니다.

약간의 물기를 없애는 한 가지 쉬운 방법은> <^ v 대신 숫자를 사용하는 것입니다. 하지만 그만한 가치가 있다고 생각하지 않습니다.

답변

Turtlèd , 146 바이트

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],

이 프로그램은 I / O를 다르게 취합니다. 마지막 행을 포함하여 공백으로 각 행을 종료하십시오. Turtlèd는 문자의 2 차원에 그리드를 사용하므로 개행을 좋아하지 않습니다.

온라인으로 사용해보십시오!

루프의 경우 0, 정지의 경우 1

일반적인 설명 :

그리드에 입력을 쓴 다음 실제로 화살표가 그리드 주위의 경로를 따라 가면서 각 화살표를 *로 바꾸고 char var의 방향을 저장합니다. *, 화살표가 발견되면 프로그램이 중지되지 않으므로 char var를로 설정 0하고 루프를 종료하십시오. 그렇지 않으면 그리드의 끝에 도달하여 루프를 종료합니다. char var를 작성합니다. 그리드의 끝에 도달하면 char var에 저장된 방향을 사용하여 그리드로 돌아가고 1중지를 위해 char var를로 설정합니다 . char var가 실제로 방향이 아닌 0 인 경우 여전히 거기에 있으므로 다시 돌아올 필요가 없으며 다시로 설정합니다 0. 그리드를 지우고 char var 1를 중지합니다 0.

답변

JavaScript (Node.js), 80 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?f(a,v=+c?c-2||v:c+n,x-v,u):!c

Try it online!

JavaScript (Node.js), 86 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?c>' '<=f(a,v=+c?c-2||v:c+n,x-v,u):0

Try it online!

답변

JavaScript (ES6), 158 127 bytes

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c

Takes input as a two-dimensional character array and returns true for halting and false for an infinite loop. Works by setting visited direction characters to ~s as it recursively traverses them. Edit: Saved 31 bytes by updating my direction vector before recursing.

Abusing the instruction characters (1=^ 4=< 5=. 6=> 9=v) takes me down to 101 bytes:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c

답변

SmileBASIC, 158 145 bytes

If the same arrow is encountered more than once, the program will never halt.
When the instruction pointer passes an arrow, it’s replaced with a different symbol, which will cause the function to return 0 if it’s reached again.
If the IP goes out of bounds, it returns 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END

Takes input as an array of strings. <any non-digit chracter>,1,2,3,4 = .,>,<,v,^