Autômato linearmente limitado
Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto. Sua fita é limitada e, portanto, finita. Ele só consegue resolver problemas que usem uma quantidade de memória que possa caber dentro da fita usada para entrada. Se por acaso utilizarmos um alfabeto de fita maior que o alfabeto de entrada então teremos um incremento da memória disponível por até um fator constante, por isso se tivermos uma entrada de tamanho na quantidade de memória disponível será linear em relação a n. Apesar de suas restrições os ALLs são bastantes potentes, podemos citar que os decisores para o problema da aceitação de um AFD para uma dada entrada, para o problema da vacuidade de um dado AFD, para o problema da aceitação de uma gramática livre de contexto e para a vacuidade de uma dada gramática livre de contexto são todos ALLs.
Autômatos linearmente limitados são aceitadores para a classe de linguagens sensíveis ao contexto. A única restrição colocada nas gramáticas para tais linguagens é que não há produção do que mapeia uma cadeia para uma cadeia mais curta. Assim, nenhuma derivação de uma cadeia em uma linguagem sensível ao contexto pode conter uma forma sentencial mais do que a cadeia em si. Uma vez que existe uma correspondência um-para-um entre autômatos linearmente limitados e tais gramáticas, não mais do que a fita ocupada pela cadeia original é necessária para a cadeia a ser reconhecida pelo autômato.
Em 1960, Myhill introduziu um modelo de autômato hoje conhecida como autômato linearmente limitado determinístico. Pouco depois, Landweber provou que as linguagens aceitas por um ALL determinístico são sempre sensíveis ao contexto. Em 1964, Kuroda introduziu o modelo mais geral (não determinístico) de autômatos linearmente limitados, e mostrou que as linguagens aceitas por eles são precisamente as linguagens sensível ao contexto.
Em seu artigo seminal, Kuroda afirmou também dois desafios de pesquisa, que posteriormente se tornaram notoriamente conhecidos como os "problemas ALL": O primeiro problema ALL é se a classe de linguagens aceitas pelo ALL é igual à classe de linguagens aceitas pelo ALL determinístico. Este problema pode ser formulado de forma sucinta na linguagem da teoria da complexidade computacional como: O segundo problema ALL é se a classe de linguagens aceitas por um ALL é fechada sob complementação. Como já observado por Kuroda, uma resposta negativa ao segundo problema ALL implicaria uma resposta negativa ao primeiro problema. Mas o segundo problema ALL tem uma resposta afirmativa, o que está implicado pelo teorema Immerman-Szelepcsényi, provado apenas mais de 20 anos depois que o problema foi levantado. Ainda em 2011, o primeiro problema ALL permanece em aberto.
