허용 번호 매기기
Admissible numbering계산가능성 이론에서 허용 가능한 숫자는 표준 번호 부여로 변환하거나 표준 번호 부여에서 변환할 수 있는 부분 계산가능함수 집합의 열거(숫자)이다.이러한 번호 매기기를 허용 가능한 번호 매기기 및 허용 가능한 프로그래밍 시스템이라고도 한다.
로저스의 등가성 정리는 모든 수용 가능한 프로그래밍 시스템이 번호 부여 이론의 형식적 의미에서는 서로 동등하다는 것을 보여준다.
정의
Kleene에 의한 계산가능성 이론의 공식화는 T 술어를 사용하여 정의된 특정한 범용 부분 계산 함수 ψ(e, x)로 이어졌다.이 함수는 부분 계산 가능하다는 점에서 보편적이며, 모든 x에 대해 f(x) = ψ(e,x)과 같은 e가 있다. 여기서 평등이란 양쪽 모두 정의되지 않았거나 둘 다 정의되어 있고 동등하다는 것을 의미한다.ψe(e,x)에 대해 ((x)를 쓰는 것이 일반적이다. 따라서 ψ0, ψ1, ...의 순서는 모든 부분 계산 가능한 함수의 열거다.그러한 열거는 공식적으로 부분 계산 가능한 함수의 계산 가능한 번호라고 불린다.
부분 함수의 임의 번호 지정 η은 다음과 같은 경우 허용 가능한 번호 지정으로 정의된다.
- 함수 H(e,x) = ηe(x)는 부분 계산 가능한 함수다.
- 모든 e에 대해 ηe = ψ과f(e) 같은 총 계산 가능한 함수가 있다.
- 모든 e에 대해 ψe = η과g(e) 같은 총 계산 가능한 함수 g가 있다.
여기서, 첫 번째 탄환에서는 숫자 지정을 계산할 수 있어야 하고, 두 번째 탄환에서는 숫자 지정 for에 대한 모든 지수를 효과적으로 숫자 지정 ψ에 대한 지수로 변환할 수 있어야 하며, 세 번째 탄환에서는 숫자 지정 ψ에 대한 지수로 효과적으로 변환할 수 ψ에 대한 지수를 숫자 지정 η에 대한 지수로 변환할 수 있어야 한다.
로저스의 등가 정리
Hartley Rogers Jr.는 부분 계산 가능한 함수의 숫자 η은 모든 e에 대해 ηe = ψp(e) (Soare 1987:25)와 같이 계산 가능한 총 바이어싱 p가 있는 경우에만 허용된다는 것을 보여주었다.
참고 항목
참조
- Y.L. 에르쇼프(1999), "숫자의 이론", 계산가능성 이론 핸드북, E.R. 그리퍼(ed.), 엘스비에르, 페이지 473–506. ISBN978-0-444-89882-1
- M. 마흐티와 P.영(1978), 알고리즘의 일반 이론에 대한 소개, 노스 홀랜드, 1978.ISBN 0-444-00226-X
- H. Rogers, Jr. (1967), 재귀적 기능과 유효 계산 가능성 이론, 제2판 1987, MIT 프레스.ISBN 0-262-68052-1(페이퍼백), ISBN 0-07-053522-1
- R. Soare(1987), 재귀적으로 셀 수 있는 세트와 도, Perspects in Mathematical Logic, Springer-Verlag.ISBN 3-540-15299-7
