이것은 경찰과 도둑 언어를 정의하고 튜링 완료를 증명하는 데 중점을 둡니다.

이것이 경찰의 실입니다. 강도의 실이 여기 있습니다 .

경찰

경찰은 두 가지를 준비합니다.

• 프로그래밍 언어 또는 기타 계산 시스템의 공식 사양. (전산 시스템은 아래에 정의되어 있습니다.)

• 아래의 엄격한 정의에 따라 시스템이 튜링 완료되었다는 증거.

당신은 당신의 언어에 대한 당신의 사양을 게시 할 것이고, 강도는 튜링 완전성을 증명함으로써 그것을 “크랙”하려고 시도 할 것입니다. 1 주일 이내에 제출물에 금이 가하지 않으면 제출물을 안전하다고 표시하고 증거를 게시 할 수 있습니다. (수정할 수없는 한 누군가 증거에서 결함을 발견하면 답변이 무효화 될 수 있습니다.)

이것은 인기 대회따라서 가장 많은 표를 얻었으며 금이 가거나 무효화되지 않은 답이 승자가됩니다. 도전은 개방적입니다-나는 대답을 받아들이지 않을 것입니다.

이러한 과제를 해결하기 위해 계산 시스템은 다음 네 가지로 정의됩니다.

• A “프로그램 세트” P. 이것은 문자열, 정수, 이진 트리, 격자의 픽셀 구성 등과 같이 셀 수없이 무한하게 설정됩니다 (그러나 아래의 기술 제한 참조).

• “input set” I은 셀 수없이 무한한 집합 P이 될 수 있으며 (그렇더라도) 같은 집합 일 필요는 없습니다 .

• “출력 세트” O는 유사하게 셀 수없이 무한하며, 같 P거나 같지 않을 수 있습니다.I

• 출력 제조 결정적 기계적 절차 o프로그램 p입력 i, p, i및 o의 구성원 P, I및 O각각이. 이 절차는 원칙적으로 튜링 머신 또는 다른 추상 계산 모델에서 구현 될 수 있어야합니다. 물론 프로그램과 입력에 따라 절차가 중단되지 않을 수 있습니다.

세트 P, I그리고 O당신이 계산 가능한 방식으로 문자열로 표현할 수 있도록해야합니다. (대부분의 합리적인 선택은 중요하지 않습니다.이 규칙은 멈추지 않는 튜링 머신 세트와 같은 이상한 세트를 선택하지 못하게하기 위해 존재합니다.)

튜링 완성도는 다음과 같이 정의됩니다.

• 임의의 계산 가능한 부분 함수 f행 I에 O, 프로그램이 존재 p에 P부여하도록 p입력 i, 출력 인 f(i)경우 f(i)의 값을 가진다. (그렇지 않으면 프로그램이 중단되지 않습니다.)

상기 정의에서 “계산 가능”이라는 단어는 “튜링 머신을 사용하여 계산 될 수있다”를 의미한다.

참고도 있다는 규칙 110 도 비트 순환 태그는 ,이 정의에 의해 튜링 완료 그들은 필요한 입출력 구조를 가지고 있지 않기 때문에. 우리가 정의로 람다 계산법은 오래로, 튜링 I과 O로 교회 숫자 . (그것은 튜링 완성되지 않은 우리가 가지고가는 경우 I와 O일반적으로 람다 표현식이 될 수 있습니다.)

언어 구현을 제공 할 필요는 없지만 원하는 경우 답변에 언어를 포함 할 수 있습니다. 그러나 어떤 식 으로든 언어를 정의하기 위해 구현에 의존해서는 안됩니다. 사양 자체가 완전해야하며 사양과 구현 사이에 모순이있는 경우 구현의 버그로 처리해야합니다.

답변