랜덤 액세스 튜링 머신

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "랜덤 액세스 튜링 머신" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학 분야인 계산 복잡성에서, 랜덤 액세스 튜링 기계는 특히 DLOGTIME 및 로그 계층 구조와 같이 로그 시간을 사용하는 클래스에 대해 작은 복잡성 클래스에 대해 말할 때 사용되는 튜링 기계의 확장이다.

정의

랜덤 액세스 튜링 머신에는 이진 어휘를 수용하는 로그 공간의 특별한 포인터 테이프가 있다.튜링 기계는 포인터 테이프의 이진 번호가 'p'일 때 튜링 기계가 작업 테이프에 입력의 pth 기호를 기록할 정도로 특수한 상태를 가지고 있다.

포인터 테이프 기능은 튜링 기계가 전체 입력 위로 이동하는 데 시간을 들이지 않고 입력의 문자를 읽을 수 있도록 한다.이는 선형 시간 미만을 사용하는 복잡성 클래스의 경우 필수 사항이다.

참조

• Neil Imerman 서술적 복잡성(1999 Springer), 5장