공허 문제를 결정할 수없는 가장 간단한 계산 모델은 무엇입니까?
계산 모델의 공허 문제 (예 : 유한 상태 오토 마톤, 교류 푸시 다운 오토 마톤, 카운터가있는 경계 오류 양자 오토 마톤, 결정적 LBA 등)는 해당 머신에 대해이 머신이 인식 / 정의한 언어인지 여부를 결정하는 것입니다. 비었다. 여기서 기계에 대한 설명은 유한해야합니다!
나는 “가장 단순한”이라는 단어가 약간 모호하다는 것을 알고 있습니다. 비교할 수없는 계산 모델에 대해 둘 이상의 답변이있을 수 있습니다.
특별한 말로, 나는 단항과 이진 알파벳에 개별적으로 초점을 맞춤으로써 질문이 더 흥미로워 질 것이라고 믿습니다.
정지 문제를 결정할 수있는 많은 계산 모델이 있지만 공허 문제 (및 일부 다른 문제)는 결정 불가능합니다 (예 : 선형 경계 오토마타 (LBA)) .
답변
아마 당신은 이미 당신의 가방에 이것을 가지고 🙂
- 단항 알파벳 (Minsky61)을 통한 양방향 하나의 카운터 머신.
- 양방향 약한 카운터 머신 (카운터는 계산에 영향을 미치지 않지만 카운터가 0에 도달하면 머신이 정지됨) [1].
- 양자 1 카운터 오토마타 [2].
이진 알파벳을 사용하면 공허함을 다음과 같이 결정할 수 없습니다.
-
하나의 무제한 카운터와 하나의 푸시 다운 저장소가있는 편도 기계는 최대 하나의 반전을 만듭니다 [3].
-
여러 역전 경계 카운터를 갖는 양방향 기계 결정 론적 유한 오토마타 (한정된 언어 이상) [3].
-
상태 비 저장 (전환은 스캔 된 기호에만 의존) 각 헤드가 입력 테이프에서 한 번만 반전하더라도 2- 헤드 2 방향 결정적 유한 오토마타 [4].
편집 : 경계에서 :
- (공개 문제) 공허 문제는 비 한정 언어에 대해 하나의 반전 경계 카운터를 갖는 양방향 비 결정적 유한 오토마타에 대해 결정 가능한가? (한정된 언어로 결정할 수있다 [5])
[1] at 흥찬. 양방향 약 카운터 기계에서 . 수학 시스템 이론 01/1987;
[2] Richard F. Bonner, Rusins Freivalds 및 Maksim Kravtsev. 2001. 카운터를 사용한 양자 대 확률 적 일 원형 유한 오토마타 . 정보학의 이론과 실천에 관한 28 차 회의에서 진행되는 정보학 : 정보학의 이론과 실천 (SOFSEM ’01), 레 sz 파콜 스키 (Leszek Pacholski), 피터 루지 카 (Eds.). Springer-Verlag, London, UK, UK, 181-190.
[3] 오스카 H.이 바라. 1978. 리버스 바운드 멀티 카운터 머신 및 그 결정 문제 . J. ACM 25, 1 (1978 년 1 월), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin,상태 비 저장 멀티 헤드 오토마타 : 계층 및 공허 문제 , 이론적 컴퓨터 과학, 볼륨 411, 제 3 권, 2010 년 1 월 6 일, 페이지 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. 하나의 반전 한계 카운터를 가진 양방향 nfa에 대한 공허 문제 . Proc. 열 세번째 Int. 증상 알고리즘 및 계산 (2002)