BlooP
BlooP(Bounded Loop)는 Douglas Hofstadter가 1979년 출간한 《Gödel, Escher, Bach》에서 계산 가능성과 수학적 함수를 설명하기 위해 제시한 작은 교육용 프로그래밍 언어다. 이름은 bounded loop에서 유래했으며, 반복 횟수를 미리 정한...
| 정식 명칭 | Bounded Loop |
|---|---|
| 분류 | 교육·수학용 프로그래밍 언어 |
| 설계자 | Douglas Hofstadter |
| 소개 작품 | 《Gödel, Escher, Bach》 |
| 등장 | 1979년 |
| 계산 모델 | 유계 반복 |
| 표현 능력 | 원시 재귀 함수 |
| 튜링 완전성 | 튜링 불완전 |
| 핵심 제어 | 반복 횟수가 유계인 LOOP |
| 프로그램 성질 | 정의된 유계 반복 프로그램의 종료 |
| 관련 언어 | FlooP |
| 연구 분야 | 계산 가능성, 재귀 이론 |
| 주요 용도 | 계산 이론 교육 |
BlooP(Bounded Loop)는 Douglas Hofstadter가 1979년 출간한 《Gödel, Escher, Bach》에서 계산 가능성과 수학적 함수를 설명하기 위해 제시한 작은 교육용 프로그래밍 언어다. 이름은 bounded loop에서 유래했으며, 반복 횟수를 미리 정한 범위 안에서만 실행하는 유계 반복 구문을 주요 제어 구조로 사용한다. 실제 응용 프로그램을 대규모로 작성하는 산업용 언어라기보다 계산 모델의 표현력과 그 한계를 명확하게 보여주기 위한 수학적 표기 언어에 가깝다.[1]
BlooP에서는 실행 전에 유한한 반복 경계를 결정할 수 있는 반복문을 사용해 수치 계산 절차를 구성한다. 반복문의 종료 조건을 임의로 무한히 기다리도록 만들지 않고 정해진 횟수 이내에 계산을 끝내는 구조를 취하기 때문에, 언어로 작성한 프로그램은 해당 실행 모델의 전제 아래 종료한다. 이 방식은 일반적인 WHILE 문이 제공하는 무제한 반복과 구별된다. 프로그램은 자연수와 변수, 단순한 계산 명령으로 여러 정수 함수를 표현할 수 있다.
BlooP의 계산 표현력은 수학의 원시 재귀 함수와 연결된다. 덧셈·곱셈과 많은 유한 반복 계산을 기술할 수 있지만, 원시 재귀 함수의 범위를 벗어나는 일부 전체 계산 가능 함수는 표현할 수 없다. 예를 들어 아커만 함수는 계산 가능하며 모든 입력에 대해 값을 반환하지만 원시 재귀 함수가 아니므로 BlooP의 유계 반복만으로 일반적인 형태를 표현할 수 없다. 이 차이는 프로그램의 종료가 보장되는 언어가 모든 계산 가능한 함수를 표현할 수 있는 것은 아니라는 점을 보여준다.
Hofstadter는 비교 대상으로 FlooP(Free Loop)를 소개해 무제한 반복을 허용하면 표현력이 달라진다는 사실을 설명했다. FlooP는 튜링 완전한 계산 모델이 될 수 있지만, 그 대신 임의 프로그램의 종료를 일반적으로 판정할 수 없다는 문제가 나타난다. BlooP와 FlooP는 반복 제어 하나의 차이가 계산 가능성, 종료 보장과 표현 능력에 얼마나 근본적인 영향을 주는지를 설명하는 교육용 언어 쌍이다.[2]