단순 대 중첩

튜링의 완성도 측면에서 중첩 루프만큼 강력한 단순 루프입니까?단순 대 중첩

출처

2011-01-16 banx

'강력한'이란 무엇입니까? –

'강력 함'이란 무엇을 의미합니까? 표현 가능성에 관해서는 두 가지 모두 동일합니다. 데이터 구조를 조정해야 할 수도 있습니다. – miku

질문을 편집하는 것이 중요합니까? –

튜링의 완성도 측면에서 그렇습니다.

증명 :

단계 (LOOP, FOR와 유사)의 고정 된 수의 루프를 들어 http://www.hevanet.com/cristofd/brainfuck/sbi.c

출처

2011-01-16 00:24:26

교정본과 함께 사용할 수있는 참조 자료가 있습니까? 어떤 가정하에? – banx

그러나 예를 들어 주셔서 감사합니다. 그러나 여전히 내부 while 루프를 사용하고 있습니다. 그러나 도움이 될 수있는 참고 문헌을 도울 수 있다면 공식적인 증거를 찾고 있습니다. – banx

@banx : 내가 연계 한 통역사가 잘못 쓰여졌습니다. 그러나 단순한 루프 만 사용하여 Brainfuck 해석을 작성하는 것은 상당히 간단합니다. 개념은 간단합니다. 명령 포인터를 이동하고 말한대로 반복하여 끝까지 반복하십시오. –

이 : 전체를 상상이 여기에 예를 들어, 간단한 루프를 사용하여 Brainf*** 인터프리터를 쓰고 자 할 루프의 목적은 n입니다. 외부 루프에서 i 번 루프를 수행하고 내부 루프에서 j 번 반복하는 경우에만 차이를 만들어야하는 이유는 단일 루프에서 n = i * j과 반대입니다.

프로그램에서 WHILE, GOTO 또는 유사한 구문 (할당, IF 및 고정 루프 만 허용)이 허용되지 않는다고 가정합니다. 그런 다음 이러한 모든 프로그램은 한정된 수의 단계를 거쳐 종료됩니다.

더 많은 표현 가능성에 대한 다음 단계는 반복을 허용하는 것이다. 조건에 의해 결정되며,이 조건이 항상 만족되는지 (예 : WHILE) 확실하지 않습니다. 그런 다음 프로그램이 중단되지 않을 수도 있습니다. 이 표현 유형은 Turing-completeness이라고도합니다.

이 두 가지 형태의 프로그램에는 역사적으로 같은 시간에 개발 된 primitive recursive functions과 μ-recursive functions이라는 두 가지 종류의 기능이 있습니다.

네 스팅의 수는 이에 영향을 미치지 않습니다.

출처

2011-01-16 00:36:13 miku

루프는 단순히 고정 된 단계를 계산하는 매우 간단한 시나리오로 가정합니다. 일반적으로 내부 변수는 루프의 정지 조건에 영향을줍니다. – banx

@ banx : 추가 된 텍스트. – miku

답변

관련 문제