Brainfuck 프로그램에서 무한 루프 감지

StackOverflow https://stackoverflow.com/questions/367571

문제

나는 간단하게 글을 썼다. 뇌 씨발 MATLAB 스크립트 언어의 인터프리터.(유전자 알고리즘 프로젝트의 일부로) 실행할 무작위 BF 프로그램이 제공됩니다.내가 직면한 문제는 프로그램이 상당히 많은 경우에 무한 루프를 갖고 있는 것으로 밝혀져 GA가 그 지점에서 멈춘다는 것입니다.
따라서 무한 루프를 감지하고 bf에서 해당 코드가 실행되지 않도록 하는 메커니즘이 필요합니다.
한 가지 명백한 (사소한) 사례는 다음과 같습니다.

[]

나는 이것을 감지하고 해당 프로그램 실행을 거부할 수 있습니다.
사소한 경우에 대해 기본 아이디어는 다음과 같습니다.루프의 한 번의 반복으로 현재 셀이 어떻게 변경되는지 확인합니다.변화가 음수이면 결국 0에 도달하게 되므로 유한 루프가 됩니다.그렇지 않고 변경 내용이 음수가 아니면 무한 루프입니다.
단일 루프의 경우 이를 구현하는 것은 쉽지만 중첩 루프의 경우 매우 복잡해집니다.예를 들어, (다음 (1)은 셀 1의 내용을 나타냅니다.)

++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[   While( (1) is non zero)
    --   Decrease (1) by 2
    >[   While( (2) is non zero)
        -    Decrement (2)
        <+   Increment (1) 
    >]   
    (2) would be 0 at this point
    +++  Increase (2) by 3 making (2) = 3
<]   (1) was decreased by 2 and then increased by 3, so net effect is increment

따라서 코드는 계속해서 실행됩니다.그러나 셀 1에서 수행된 +와 -의 수에 대한 순진한 검사는 -의 수가 더 많다는 것을 의미하므로 무한 루프를 감지하지 못합니다.
bf에 임의 개수의 루프가 임의로 중첩되어 있는 경우 무한 루프를 감지하는 좋은 알고리즘을 생각할 수 있는 사람이 있습니까?

편집하다:정지 문제가 일반적으로 해결 불가능하다는 것은 알고 있지만 특별한 경우 예외가 있는지는 확실하지 않았습니다.예를 들어, Matlab은 bf 프로그램의 중단을 결정할 수 있는 Super Turing 기계로 작동할 수도 있습니다.제 말이 엄청나게 틀렸을 수도 있지만, 그렇다면 정확히 그 방법과 이유를 알고 싶습니다.

두 번째 편집:나는 무한 루프 탐지기라고 주장하는 것을 작성했습니다.아마도 일부 엣지 케이스를 놓쳤을 수도 있습니다.Turing의 클러치)이지만 현재로서는 나에게 적합한 것 같습니다.의사코드 형식에서는 다음과 같습니다.

subroutine bfexec(bfprogram)
begin
    Looping through the bfprogram,
        If(current character is '[')
            Find the corresponding ']'
            Store the code between the two brackets in, say, 'subprog'
            Save the value of the current cell in oldval
            Call bfexec recursively with subprog
            Save the value of the current cell in newval
            If(newval >= oldval)
                Raise an 'infinite loop' error and exit
            EndIf
        /* Do other character's processings */
        EndIf
    EndLoop
end
도움이 되었습니까?

해결책

선형 유전자 프로그래밍을 사용했을 때, 나는 단일 프로그램이 생애 동안 할 수있는 지침의 수에 상한을 사용했습니다. 나는 이것이 두 가지 방식으로 합리적이라고 생각합니다. 어쨌든 중단 문제를 해결할 수는 없으며 계산하는 데 너무 오래 걸리는 프로그램은 어쨌든 더 많은 시간을 할애 할 가치가 없습니다.

다른 팁

앨런 튜링은 당신과 함께 한마디를 갖고 싶습니다.

http://en.wikipedia.org/wiki/halting_problem

이 프로그램이 무한 루프로 실행되는지 여부를 감지 할 수있는 프로그램을 작성했다고 가정 해 봅시다. 이 프로그램이 Brainfuck 프로그램을 분석하기 위해 Brainfuck로 작성되었다고 간단하게 말하자.

이제 새로운 프로그램을 만들기 위해 Checker 프로그램을 확장한다고 가정 해 봅시다. 이 새로운 프로그램은 입력이 무한정 루프되면 즉시 종료되며, 입력이 어느 시점에서 종료 될 때 영원히 루프합니다.

이 새로운 프로그램 자체를 입력하면 결과는 무엇입니까?

이 프로그램이 실행될 때 영원히 반복되면 자체 정의에 의해 입력으로 실행될 때 즉시 종료해야합니다. 그 반대. 체커 프로그램은 존재할 수 없습니다. 그 존재는 모순을 의미하기 때문입니다.

앞에서 언급했듯이, 당신은 본질적으로 유명한 중단 문제를 재조정하고 있습니다.http://en.wikipedia.org/wiki/halting_problem

에드. 나는 위의 반박이 내 자신의 것이 아니라는 것을 분명히하고 싶지만, 본질적으로 1936 년에 Alan Turing이 주었던 유명한 반증입니다.

BF의 상태는 단일 숯입니다.

내가 당신이라면, 나는 모든 "]] "(또는 한 번 랜드 (1, 100)] "S*)에서 BF 통역 상태의 해시를 가져 가서 해시 세트가 독특하다고 주장합니다.

두 번째 (또는 그 이상) 시간은 특정 해시를 볼 때 전체를 제쳐두고 있습니다.

세 번째 (또는 그 이상) 시간은 특정 해시를보고, 나는 전체 상태를 저장된 하나와 비교하고 일치하는 경우, 나는 종료합니다.

모든 입력 명령 ( '.', IIRC)에서 저장된 상태와 해시 목록을 재설정합니다.

최적화는 접촉 된 상태의 일부만 해시하는 것입니다.

나는 정지 문제를 해결하지 않았다 - 나는 무한 루프를 감지하고있다. 달리는 동안 프로그램.

*랜드는 루프 기간과 독립적으로 점검하는 것입니다.

무한 루프를 감지 할 수는 없지만 프로그램에 너무 많은 시간이 걸리는지 감지 할 수 있습니다.

명령을 실행할 때마다 카운터를 증가시켜 타임 아웃을 구현하십시오 (예 : <, >, +, -). 카운터가 관찰에 의해 설정된 많은 수에 도달하면 프로그램을 실행하는 데 시간이 오래 걸린다고 말할 수 있습니다. 당신의 목적을 위해, "매우 길다"와 무한은 좋은 근사치입니다.

이미 언급했듯이 이것은 중단 문제입니다. 그러나 귀하의 경우 해결책이있을 수 있습니다. 중단 문제는 무제한 메모리가있는 튜링 머신에 관한 것입니다.

메모리 상한이 있다는 것을 알고 있다면 (예 : 10 개 이상의 메모리 셀을 사용하지 않는다는 것을 알고 있음) 프로그램을 실행하여 중지 할 수 있습니다. 아이디어는 계산 공간이 계산 시간을 결합한다는 것입니다 (한 단계에서 둘 이상의 셀을 쓸 수 없기 때문에). 다른 메모리 구성을 가질 수있는만큼 많은 단계를 실행 한 후에는 깨질 수 있습니다. 예를 들어 256 개의 조건을 가진 3 개의 셀이 있다면 최대 3^256 개의 다른 상태를 가질 수 있으므로 많은 단계를 실행 한 후에는 중지 할 수 있습니다. 그러나주의 포인터 및 레지스터와 같은 암시 적 셀이 있습니다. 모든 상태 구성을 저장하고 이미 가지고 있던 상태를 감지하자마자 감정 루프가 있습니다. 이 접근법은 런타임에 확실히 훨씬 나은 것이지만 훨씬 더 많은 공간이 필요합니다 (여기서 구성을 해시하는 데 적합 할 수 있음).

이는 정지 문제는 아니지만 1000셀 BF 시스템과 같은 제한된 시스템에서도 정지를 감지하려고 시도하는 것은 여전히 ​​합리적이지 않습니다.

다음 프로그램을 고려해보세요:

+[->[>]+<[-<]+]

이 프로그램은 전체 메모리를 채울 때까지 반복되지 않으며 단지 1000개의 셀에 대해 약 10^300년이 걸립니다.

내 머리 꼭대기에서 (그리고 나는 틀릴 수 있음), 프로그램 자체를 실제로 실행하지 않고 프로그램에 무한 루프가 있는지 여부를 감지하기가 조금 어려울 것이라고 생각합니다.

프로그램의 일부의 조건부 실행은 프로그램의 실행 상태에 따라 달라 지므로 실제로 프로그램을 실행하지 않고 프로그램의 특정 상태를 알기가 어렵습니다.

그렇지 않다면 필요하다 무한 루프가있는 프로그램이 실행되면 "명령어 실행"카운터를 사용하려고 시도하고 유한 수의 지침 만 실행할 수 있습니다. 이런 식으로, 프로그램에 무한 루프가있는 경우, 통역사는 무한 루프에 갇힌 프로그램을 종료 할 수 있습니다.

내가 올바르게 기억한다면, 정지 문제 증명은 자기 참조와 관련된 일부 극단적인 경우에만 해당됩니다.그러나 무한 루프 감지기를 만들 수 없는 이유에 대한 실제적인 예를 보여주는 것은 여전히 ​​쉽지 않습니다.

고려하다 페르마의 마지막 정리.모든 숫자(또는 이 경우 3개의 숫자)를 반복하고 그것이 정리에 대한 반례인지 감지하는 프로그램을 만드는 것은 쉽습니다.그렇다면 중지되고, 그렇지 않으면 계속됩니다.

따라서 무한 루프 검출기가 있다면 이 정리와 다른 많은 정리(반례 검색으로 축소할 수 있다면 아마도 다른 모든 정리)를 증명할 수 있어야 합니다.

일반적으로 숫자를 반복하고 특정 조건에서만 중지하는 프로그램에는 해당 조건이 충족될 수 있는지 증명하기 위한 일반 정리 증명이 필요합니다.이것이 바로 루핑의 가장 간단한 사례입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top