Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?

Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?

Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej maszyny język rozpoznawany / definiowany przez tę maszynę jest pusty. Tutaj opis maszyny powinien być skończony!

Wiem, że słowo „najprostsze” jest trochę niejasne. W przypadku niektórych nieporównywalnych modeli obliczeniowych może być więcej niż jedna odpowiedź.

Jako specjalną uwagę uważam, że pytanie stałoby się bardziej interesujące poprzez osobne skupienie się na jednostkowych i binarnych alfabetach.

Należy zauważyć, że istnieje wiele modeli obliczeniowych, dla których problem zatrzymania jest rozstrzygalny, ale problem pustki (i niektóre inne problemy) jest (są) nierozstrzygalny, np. Automaty liniowe (LBA) .

Prawdopodobnie masz je już w torbie :-)

• Dwukierunkowa maszyna licznikowa nad jednoznacznym alfabetem (Minsky61).
• Liczniki dwukierunkowe słabe (licznik nie ma wpływu na obliczenia, ale maszyna zatrzymuje się, jeśli licznik osiągnie zero) [1].
• Automaty do liczników kwantowych [2].

W przypadku binarnych alfabetów pustka pozostaje nierozstrzygalna dla:

• Maszyny jednokierunkowe z jednym niepowiązanym licznikiem i jednym sklepem pushdown, który dokonuje co najwyżej jednego cofnięcia [3].

• Maszyny dwukierunkowe deterministyczne automaty skończone z wieloma licznikami ograniczającymi odwrócenie (nawet w ograniczonym języku) [3].

• Bezstanowe (przejścia zależą tylko od skanowanego symbolu) 2-głowicowe 2-kierunkowe deterministyczne automaty skończone, nawet gdy każda głowica dokonuje tylko jednej zmiany na taśmie wejściowej [4].

Edycja : na granicy:

• (Problem otwarty) Czy problem pustki jest rozstrzygalny dla dwustronnych niedeterministycznych automatów skończonych z jednym licznikiem ograniczonym odwróceniem w stosunku do języków nieograniczonych? (w przypadku języków z ograniczeniami jest to rozstrzygalne [5])

[1] Chan tat-hang. Na dwukierunkowych słabych licznikach . Teoria systemów matematycznych 01/1987;
[2] Richard F. Bonner, Rusins ​​Freivalds i Maksim Kravtsev. 2001. Kwant kontra probabilistyczne jednokierunkowe skończone automaty z licznikiem . W materiałach 28. Konferencji nt. Aktualnych trendów w teorii i praktyce informatyki Pieszczany: teoria i praktyka informatyki (SOFSEM '01) Leszek Pacholski i Peter Ruzicka (red.). Springer-Verlag, Londyn, Wielka Brytania, Wielka Brytania, 181–190.
[3] Oscar H. Ibarra. 1978. Maszyny z licznikami zwrotnymi i ich problemy decyzyjne . J. ACM 25, 1 (styczeń 1978), 116–133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin,W przypadku bezpaństwowych automatów wielogłowicowych: Hierarchie i problem pustki , Theoretical Computer Science, tom 411, wydanie 3, 6 stycznia 2010 r., Strony 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. O problemach z pustką dla dwukierunkowej nfa z jednym licznikiem ograniczonym przez odwrócenie . W Proc. Trzynasty Int. Symp. w sprawie algorytmów i obliczeń (2002)