카이틴 상수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

알고리즘 정보 이론 의 컴퓨터 과학 하위 분야 에서, 카이틴(또는 차이틴 또는 카이틴 오메가)상수(Chaitin omega number) [1] 또는 정지 확률은 프로그램이 무작위로 생성되는 값의 계산(랜덤생성시)으로 인해 정지()할 확률을 나타내는 실수이다.

이 수는 Gregory Chaitin에 의해 설정되었다.

컴퓨터 프로그램과 관련해서 컴퓨터의 작동을 단위로 하고, 컴퓨터의 작동을 부분적으로 구성하는 프로그램들을 그 하위단위로 가정했을때, 그 프로그램들중 임의의 프로그램이 작동을 멈추지 않는 경우(일종의 정지상태-)의 확률을 예상해 볼 수 있다.

카이틴(1975)에 의해 소개 된 카이틴(Chaitin)의 상수는, 보편적인 접두어가없는 (자체 분리) 튜링 기계의 정지 확률이다 . 모든 카이틴 상수는 동시에 계산 가능하게 열거 가능하며 (계산 가능, 증가, 수렴되는 합계 수차의 제한) 알고리즘적으로 무작위 (이진수확장은 알고리즘 무작위순서 임)이므로 계산할 수 없다 (Chaitin 1975).

이러한 설정으로부터 카이틴 상수는 다음과 같은 정의가 제안된다.

카이틴 상수의 연산 값은 머신(기계)에 따라 크게 달라진다. 특정 범용 튜링 머신의 경우

같이 보기[편집]

각주[편집]

  1. mathworld.wolfram.com, Chaitin's Constant. Retrieved 28 May 2012