Máquinas de turing e linguagens formais são o mesmo objeto matemático?

O objetivo de Turing ao construir seu conceito era formalizar como os humanos fazem o raciocínio abstrato.

Agora me corrija se eu estiver errado, mas esse raciocínio parece apenas um exercício em que você manipula um conjunto de declarações formais, ou seja, strings sem nenhuma semântica associada a ele.

Portanto, se as máquinas de Turing são iguais ao raciocínio, existe um isomorfismo (ou algo parecido) entre linguagens formais e máquinas de Turing?

Não é bem assim. Uma máquina de Turing é descrita por este objeto matemático:

Onde

• $Q$ é um conjunto finito de estados
• $\Sigma$é um alfabeto , um conjunto finito de símbolos
• $\delta : Q \times \Sigma \rightarrow Q \times \Sigma \times\{\Leftarrow, \Rightarrow\}$ é uma função de transição
• $\mathcal H \subseteq Q$é o conjunto de estados de parada
• $q_0 \in Q$ é o estado inicial
• $b \in \Sigma$ é o símbolo "em branco"

A máquina usa alguma sequência de entrada, $x \in \Sigma*$e usa a função de transição para atualizar iterativamente símbolos individuais nessa sequência até $\delta$ retorna um estado pertencente a $\mathcal H$. Nesse ponto, dizemos que a máquina parou - o que pode ou não fazer.

Comparado a tudo isso, linguagens formais são objetos muito mais simples. Um idioma é apenas um subconjunto do conjunto de todas as strings sobre algum alfabeto. Em outras palavras,$\mathcal L \subseteq \Sigma^*$, Onde $*$é o operador estrela Kleene .

A conexão é que as máquinas de Turing podem ser usadas para definir linguagens formais. Por exemplo:

Define a linguagem formal $\mathcal L$ em termos da máquina de Turing $\mathcal M$. Para um idioma,$\mathcal L$, se existir uma máquina de Turing que interrompa se e somente se sua entrada pertencer a $\mathcal L$, o idioma será chamado de reconhecível por Turing . Algumas linguagens não podem ser definidas por nenhuma máquina de Turing, o que significa que elas não são computáveis - nenhum processo finito pode decidir se uma sequência arbitrária pertence ou não à linguagem.

Linguagens formais não são iguais às máquinas de Turing, mas o reconhecimento de Turing tem um lugar interessante no estudo das linguagens formais. Na hierarquia de Chomsky, uma linguagem Tipo 0 é uma linguagem que pode ser enumerada por qualquer gramática formal, e isso equivale a ser reconhecível por uma máquina de Turing! Gramáticas formais e máquinas de Turing são apenas dois dos muitos modelos de computação que são igualmente poderosos!

Geralmente, acredita-se que todo modelo de computação faz a mesma distinção entre linguagens computáveis ​​e não computáveis ​​- essa noção é chamada de tese de Church-Turing .

Edição: Minha terminologia estava desligada quando eu escrevi isso inicialmente. Uma linguagem decidível de Turing pode ser decidida por uma máquina que sempre pára e fornece um sim ou não definitivo para determinar se sua entrada pertence à linguagem. Quando exigimos apenas que a máquina aceite membros, mas não pode necessariamente rejeitar não membros, o idioma associado é chamado de Turing reconhecível ou, mais comumente, recursivamente enumerável. Os idiomas reconhecíveis de Turing são equivalentes aos idiomas que podem ser gerados por gramáticas irrestritas.

Algumas linguagens nem são recursivamente enumeráveis ​​- por exemplo, o conjunto de todas as máquinas de Turing que não param é totalmente irreconhecível. Há um idioma correspondente a esse conjunto que não pôde ser gerado por nenhuma gramática, mas que ainda pode ser chamado de "linguagem formal". Por essa definição, não há mapeamento completo das máquinas de Turing para linguagens formais e, definitivamente, não há isomorfismo entre as duas.

Não, eles não são a mesma coisa. Um idioma é um conjunto de palavras sobre algum alfabeto finito. Uma máquina de Turing é uma tupla de 7, conforme definido na Wikipedia .

Para alguns idiomas, é conveniente caracterizá-los por uma TM que os reconheça. Para cada idioma que pode ser reconhecido por uma TM, há um número infinito de TMs que reconhecem o mesmo idioma; portanto, você precisa impor alguns critérios adicionais se quiser torná-lo único.

Isso pode parecer um bom começo para um isomorfismo, mas infelizmente existem infinitas linguagens que não podem ser reconhecidas pelas TMs. Isso pode ser visto por um simples argumento de contagem. O conjunto de todas as palavras possíveis sobre um alfabeto fixo é isomórfico para os números naturais. Portanto, o conjunto de todos os idiomas nesse alfabeto (= o conjunto de todos os subconjuntos de palavras) é incontável. Por outro lado, existem apenas muitas máquinas de Turing. Portanto, não apenas o "reconhecimento" não pode ser transformado em um isomorfismo, como também não pode haver nenhum isomorfismo, pois isso implicaria que o conjunto de TMs tenha a mesma cardinalidade que o conjunto de idiomas.