Existem autômatos não finitos?

Na teoria dos autômatos, todos nós lemos autômatos como autômatos finitos, desde o início. O que eu quero saber é: por que os autômatos são finitos? Para ser claro, o que é um autômato finito - o alfabeto, a linguagem, as seqüências de caracteres feitas com expressões regulares ou o quê? E há (em teoria) algum autômato não finito?

Todos os modelos de autômatos que você normalmente encontra são representados finitamente; caso contrário, haveria inúmeras, o que significa que elas não são capturadas pelos modelos completos de Turing. Ou, no pensamento de CS, eles seriam inúteis¹.

"Autômatos finitos" são chamados finitos porque eles só têm um conjunto finito de configurações (a sequência de entrada de lado). Os autômatos de empilhamento, por exemplo, têm uma pilha que pode ter conteúdo arbitrário - existem infinitas configurações possíveis.

Nota bene: As configurações de PDAs ainda são finitamente representadas! De fato, qualquer modelo computacional que se enquadre na computabilidade de Turing deve ter configurações finamente representáveis, caso contrário, as TMs não seriam capazes de simulá-las.

1. Eu conscientemente desconsidero a hipercomputação aqui para o propósito desta pergunta.

O nome completo é "autômato de estado finito ". A parte crucial é que o estado do autômato pode ser totalmente caracterizado por um elemento de algum conjunto finito de estados discretos. Isso significa que se o estado (relevante) do autômato envolve uma variável com valor real, há um número infinito de estados potenciais (deixando de lado a finitude das representações de ponto flutuante), e o autômato não é finito.

Isso pode nunca acontecer na ciência da computação teórica, mas não é muito exótico no domínio da modelagem de seqüências de números reais. Modelos de Markov ocultos podem ser usados ​​para modelar uma sequência numérica como a saída de um sistema probabilístico que consiste em um filtro de saída para cada estado de um modelo Markov (discreto, finito) com estados não observáveis. Os filtros calculam a próxima saída com valor real de um vetor das saídas anteriores (modelo "autoregressivo"), mas o modelo subjacente de Markov é finito, pois suas probabilidades de transição dependem apenas do estado atual de Markov.

No entanto, este artigo ( texto completo ) desenvolve uma variação em que as probabilidades de transição também dependem do vetor de número real de saídas anteriores. O estado desse sistema é a combinação de um estado Markov discreto e uma tupla de números reais ("modelo Markov de estado misto"); portanto, ele pode estar em um número infinito de estados diferentes.

Em resumo, autômatos não finitos são teoricamente bem definidos e, ocasionalmente, até encontrados.

Em um autômato finito, há um pouco de finitude: o número de estados, o tamanho do alfabeto subjacente e os comprimentos das strings aceitas pela máquina.

Você certamente pode relaxar a condição de finitude neles permitindo, digamos, que a máquina tenha infinitos estados, mas se o fizer, a máquina resultante se tornará desinteressante, no sentido de que essas máquinas podem ser projetadas para aceitar qualquer idioma.

De fato, na teoria dos autômatos (que se afasta muito das origens de Kleene, Rabin e Scott), existem muitas formas de autômatos que não são finitas. Isso surge por várias razões.

Os autômatos de empilhamento , por exemplo, são autômatos com um conjunto infinito de configurações (eles têm um número finito de estados, mas a realidade é que esses devem ser considerados como 'autômatos infinitos').

Na mesma linha, existem outros exemplos de autômatos infinitos para os quais o espaço de estados é infinito, mas com muita estrutura. Por exemplo, considera-se a classe de autômatos que têm como espaço de estado um espaço vetorial (dimensão finita) e como funções de transição mapas lineares (mais algumas coisas iniciais e finais). Estes são conhecidos como autômatos ponderados sobre um campo base (devido a Schützenberger em 61). Estes podem ser minimizados e testados quanto à igualdade. Outros exemplos incluem autômatos de registro (esses autômatos têm um conjunto finito de registros e funcionam com um alfabeto infinito: eles podem comparar letras com registros e armazenar letras em registros) e a forma mais moderna de autômatos nominais(que têm a mesma expressividade, mas têm melhores fundamentos e propriedades). O vazio de tais autômatos é decidível.

$A^*$$a$$u$$ua$, e um estado está aceitando se pertencer a L). Há também um objeto final (que possui como idioma dos estados!). A existência desses dois objetos é uma maneira de explicar em alto nível por que os autômatos determinísticos podem ser minimizados e estão intimamente ligados à congruência Myhill-Nerode.

Para concluir, existem autômatos infinitos, mas os modelos que são estudados pela primeira vez em uma palestra são sempre os de estado finito.

Eu acho que a pergunta está assumindo a conclusão de que não há autômatos de estados infinitos quando existem, eles simplesmente não valem a pena ser trazidos à tona.

Na teoria dos autômatos, existe uma hierarquia de poderes de diferentes modelos virtuais. O que eu aprendi tinha 4 (que eu lembro, já faz algum tempo), o que eu encontrei na Wikipedia tem 5. O mais fraco nos autômatos de estados finitos e o mais forte são as máquinas de Turing. Existe um conceito de um nível mais poderoso do que as máquinas de Turing que é chamado livremente de hipercomputação. Muitas descrições diferentes de máquinas virtuais se enquadram em um desses níveis. As máquinas de Turing são especialmente conhecidas por vários modelos, todos com o mesmo nível de potência computacional.

Um autômato de estado infinito, pelo menos um formalmente definido, cairá em um desses níveis. Pode haver algo um pouco interessante em mostrar como uma certa definição rigorosa de um autômato de estado infinito se encaixa em um desses níveis, mas fora isso, não seria de muita utilidade, uma vez que existem máquinas virtuais muito mais estudadas que representam cada nível . É semelhante à forma como não há muito interesse em um bilhão de máquinas de Turing, pois não seria mais poderoso que uma única máquina de Turing, mas mais complicado de lidar.

Agora, se você encontrar um autômato de estado infinito que não seja equivalente a um nível existente da hierarquia, isso poderá ser interessante. Mas sem isso, os autômatos de estados infinitos já são capturados dentro da hierarquia existente e, dadas as complicações adicionais de lidar com o infinito, apenas evitamos da mesma maneira que evitamos qualquer modelo de máquina de Turing excessivamente complicado.

A versão (ingênua) infinita da máquina determinista de estados finitos é muito poderosa . Uma coisa dessas seria capaz de "memorizar" qualquer idioma, de modo que não há muito a ser aprendido considerando-os.

Por exemplo, sobre um alfabeto binário, considere um autômato na forma de uma árvore binária completa de altura infinita. Cada string possível que você poderia considerar como entrada corresponde exclusivamente a um nó da árvore, para que você possa construir uma decisão para qualquer idioma simplesmente fazendo com que os nós correspondentes aceitem estados.