GN⁺: 실무 프로그래머를 위한 Primitive Recursive Functions

기본 재귀 함수: 실무 프로그래머를 위한 안내

프로그래머들은 종종 "튜링 완전성"이라는 용어를 사용함. 특정 도메인에서는 튜링 완전하지 않음이 미덕이나 요구사항으로 여겨지기도 함. 그러나 대부분의 논의는 잘못된 정보에 기반하고 있음. 튜링 완전하지 않음이 실제로 의미하는 바는 다름. 튜링 완전성은 수학적 용어로, 매우 구체적인 의미를 가짐. 이를 다른 용도로 재해석하는 것은 허용되지 않음.

Part I: 요약

• 튜링 완전한 언어로 작성된 프로그램이 O(22N)보다 빠르게 실행된다면, 비튜링 완전한 언어로도 구현 가능함.
• 대부분의 실용적인 문제는 "두의 두의 두"보다 빠름.
• 비튜링 완전한 언어가 실용적으로 제한을 주지 않음.
• 프로그램이 종료하지 않거나, 종료하는 데 엄청난 시간이 걸리는 경우는 동일하게 취급됨.

Part II: 기계의 작동 원리

유한 상태 기계 (Finite State Machines)

• 유한 상태 기계는 문자열을 입력받아 "예" 또는 "아니오"를 반환함.
• 유한한 수의 상태를 가짐.
• 상태 전이 함수는 현재 상태와 다음 입력 기호를 받아 새로운 상태를 반환함.
• 유한 상태 기계는 무한 루프에 들어갈 수 없음.
• 유한 상태 기계는 정규 표현식과 동일한 표현력을 가짐.

튜링 기계 (Turing Machines)

• 튜링 기계는 유한 상태 기계보다 약간 더 복잡함.
• 튜링 기계는 가변 테이프를 사용하여 작동함.
• 상태 전이 함수는 현재 상태와 테이프의 현재 기호를 받아 새로운 상태, 기호, 이동 방향을 반환함.
• 튜링 기계는 함수로 작동하며, 무한 루프에 들어갈 수 있음.
• 튜링 기계는 유한 상태 기계를 시뮬레이션할 수 있음.

튜링 기계의 프로그래밍

• 튜링 기계는 무한한 테이프를 가짐.
• 튜링 기계는 사용자 제공 프로그램을 실행하지 않음. 프로그램은 기계에 하드코딩됨.
• 유니버설 튜링 기계는 다른 튜링 기계를 시뮬레이션할 수 있음.
• 튜링 기계는 파이썬과 같은 언어와 동일한 계산 능력을 가짐.

튜링 기계의 한계

• 튜링 기계로 구현할 수 없는 함수가 존재함.
• 모든 튜링 기계를 나열할 수 있지만, 모든 함수는 나열할 수 없음.
• 특정 문제(예: 정지 문제)는 튜링 기계로 해결할 수 없음.
• 튜링 기계의 강력함은 프로그램의 종료 여부를 판단할 수 없게 만듦.

Part III: 실용적인 문제로 돌아가기

기본 재귀 함수 (Primitive Recursive Functions)

• 기본 재귀 함수는 자연수의 튜플을 입력받아 자연수를 반환하는 함수임.
• zero와 succ 함수로부터 시작하여 다른 함수들을 구성함.
• 일반적인 재귀는 허용되지 않지만, 제한된 형태의 루프는 허용됨.
• 덧셈, 곱셈, 거듭제곱 등의 연산을 정의할 수 있음.
• 논리 연산자와 조건문을 정의할 수 있음.
• 데이터 구조를 표현하기 위해 숫자를 사용함.

GN⁺의 정리

• 이 글은 튜링 완전성과 기본 재귀 함수에 대한 이해를 돕기 위해 작성됨.
• 튜링 완전하지 않음이 실용적으로 어떤 의미를 가지는지 설명함.
• 유한 상태 기계와 튜링 기계의 차이점을 설명하고, 튜링 기계의 한계를 논의함.
• 기본 재귀 함수의 정의와 사용법을 설명함.
• 이 글은 프로그래머들이 튜링 완전성과 기본 재귀 함수에 대한 이해를 높이는 데 도움이 될 것임.
• 비슷한 기능을 가진 프로젝트로는 "정규 표현식"과 "유한 상태 기계"가 있음.