Pytania oznaczone «unary-languages»

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...

Czy jednokierunkowe przemienne automaty z jednym licznikiem rozpoznają niektóre jednoargumentowe nieregularne języki?

Jednokierunkowe naprzemienne automaty wypychające (1APDA) mogą rozpoznać dowolny język w (Alternacja autorstwa Chandra, Kozen i Stockmeyer, 1981) . Zastępując przechowywanie w dół 1APDA przez licznik, możemy uzyskać jednokierunkowy automat na przemian z jednym licznikiem (1ACA). Moje pytanie...