Czy wszystkie języki kontekstowe są rozstrzygalne?

Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to:

Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią.

Widziałem, że automat ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli tak jest, oznacza to, że każde obliczenie na LBA zatrzyma się w pewnym momencie (ponieważ każdy LBA byłby decydujący). Ale czuję, że mogą istnieć pewne obliczenia, które mogą działać na LBA w tym samym czasie, aby nigdy się nie zatrzymać. Na przykład możemy napisać obliczenia na LBA, które by to zrobiły

1. przeczytaj pierwszy symbol na taśmie i przejdź w prawo;
2. przeczytaj następny symbol i cofnij się w lewo.

To (bezużyteczne) obliczenie (które jest oczywiście obliczeniem LB) działałoby w nieskończoność oscylując w lewo i w prawo i nigdy się nie zatrzymywało, a zatem nie może być decydujące. Gdzie myślę źle?

Po pierwsze, wszystkie języki kontekstowe są rozstrzygalne, ponieważ mogą być zaakceptowane przez LBA (jak powiedziałeś), a maszyna Turinga ma większą moc niż LBA.

$M$$M'$$M$$M'$

Proponuję rzucić okiem na tę książkę: Wprowadzenie do języków i teorii obliczeń Johna E. Martina

strona 283: Nadal istnieją pytania dotyczące języków kontekstowych, takie jak to, czy każda CSL może zostać zaakceptowana przez deterministyczny LBA.