문제는 Arora-Barak의 저서 Computational Complexity-Modern Approach 의 연습 1.9입니다 .
RAM 튜링 머신을 랜덤 액세스 메모리가있는 튜링 머신으로 정의하십시오. 우리는 이것을 다음과 같이 공식화합니다. 기계에는 모든 배열로 초기화되는 무한 배열 A가 있습니다. 다음과 같이이 배열에 액세스합니다. 기기의 작업 테이프 중 하나가 주소 테이프로 지정되어 있습니다. 또한 기계에는 R과 W로 표시되는 두 개의 특수 알파벳 기호와 q_access로 표시되는 추가 상태가 있습니다. 머신이 q_access에 들어갈 때마다, 주소 테이프에 ‘i’R (여기서’i ‘는 i의 2 진 표시를 나타냄)을 포함하면 값 A [i]가 R 기호 옆의 셀에 기록됩니다. 테이프에 ‘i’Wa가 포함 된 경우 (여기서 a는 기계 알파벳의 일부 기호 임) A [i]는 값 a로 설정됩니다.
부울 함수 가 RAM TM에 의해 시간 T ( n ) 내에 (일부 구성 가능 T ) 계산 가능 하면 D T I M E ( T ( n ) 2 )에 있음을 보여 줍니다.
에프티(엔)
티
디티나는미디엄이자형(티(엔)2)
추가 테이프 기록 쌍 (주소 값)을 이용하여 단순 용액에 밝혀 이 테이프 크기로 될 수 있으므로, O ( T ( N ) 2 ) 와 O ( T ( n ) ) 쌍인 반면 각 쌍의 주소는 O ( T ( n ) ) 크기 일 수 있습니다 .
디티나는미디엄이자형(티(엔)삼)영형(티(엔)2)
영형(티(엔))
영형(티(엔))
답변
당신은 의견에 쓴다 :
주소는 튜링 머신에 의해 테이프에 기록되어야하므로 주소 의 크기 (예 : 문자열 길이)는 O ( T ( n ) )를 초과 할 수 없습니다 .
티(엔)영형(티(엔))
비슷한 논증을 사용하여 한계를 개선 할 수 있습니까
[The] 테이프의 크기는 와 O ( T ( n ) ) 쌍일 수 있으며 각 쌍의 주소는 O ( T ( n ) ) 크기 일 수 있습니다 .
영형(티(엔)2)영형(티(엔))
영형(티(엔))
질문에서 언급 했습니까? RAM에서 일정한 시간에 가능한 작업, 즉 작성자가 사용하는 정확한 정의를 사용하는 작업을 기억해야 할 수도 있습니다.