A mente pode ser um autômato finito e ainda inventar a máquina de Turing?

A máquina de Turing foi inventada por uma mente humana. Presumivelmente, nada menos poderoso do que uma máquina de Turing pode inventar uma máquina de Turing.

No entanto, uma máquina de Turing possui fita infinita, enquanto a mente está situada em um universo finito e, portanto, só pode ser uma MT com fita finita. Uma TM com fita finita pode ser simulada por um autômato finito, que é estritamente menos poderoso que uma Máquina de Turing. Isso parece implicar que uma máquina de Turing foi inventada por um autômato menos poderoso que uma máquina de Turing, contradizendo a premissa inicial.

Isso é um problema? Ou, a premissa inicial é falsa? É possível que um autômato finito, de alguma forma, "invente" uma máquina que é mais poderosa, uma espécie de inicialização, se você quiser?

Embora seja difícil definir formalmente "inventar", não parece que um autômato finito possa mesmo representar TMs finitas com eficácia. Por exemplo, na página da Wikipedia, ele declara que um DFA exigirá quatrilhões de estados para representar uma TM com algumas centenas de estados. Portanto, para representar apenas o subconjunto útil de TMs interrompidas, minha impressão é que uma representação do DFA provavelmente excederá qualquer capacidade computacional que tivermos. Parece haver uma grande desconexão entre DFAs e TMs, de modo que é difícil imaginar um bootstrapping plausível para ir de um para o outro.

Há também a questão relacionada de como um autômato finito pode provar o problema da interrupção das MTs.

Você realmente tem um problema de premissa. Nós não somos FSMs ou TMs. Não esqueça que todos esses dispositivos da teoria computacional são abstrações matemáticas simples compostas por uma série de axiomas e entrada limitada. Os sistemas de teoria computacional (Godel, Turing e Church) são meramente projetados para permitir que façamos provas sobre se certos tipos de funções são computáveis ​​ou não.

Por outro lado, nós:

1. filtrar informações literalmente infinitas
2. possuir consciência (o que isso significa)
3. existe no mundo físico

Uma prova simples de que não somos TMs é o que você acabou de descrever: podemos inventar Máquinas de Turing, mas a Turing Machines não pode nos inventar. É absolutamente trivial para nós ver o ponto final de uma infinidade de configurações de MT antes de executá-las (embora também existam TMs infinitas para as quais não podemos ver o endpoint), mas nenhuma TM pode determinar trivialmente o endpoint de um humano antes que ele ou ela vidas.

Existe um ditado da cartografia que pode ser muito útil aqui: O mapa não é o território

Esses sistemas axiomáticos são projetados de maneira muito inteligente para obter um conjunto minúsculo (embora importante) de idéias, mas tentar reduzir um humano às 7 tuplas e séries curtas de axiomas de uma máquina de Turing faz tanto sentido quanto reduzir humanos a qualquer outro resumo sistema axiomático. Embora esses sistemas sejam úteis para ver aspectos do mundo real, eles não são imagens completas, e não somos Máquinas de Estado Finito ou Máquinas de Turing, assim como não somos Teoria dos Números ou Teoria dos Conjuntos.

Alguns detalhes da máquina de Turing

• Uma máquina de Turing não possui fita infinita, possui fita ilimitada . Não há limite para quantos símbolos podem ser armazenados nele, mas a qualquer momento, apenas um número finito de símbolos está na fita. Portanto, embora não possamos conceber todas as execuções de uma máquina, sempre podemos conceber pelo menos alguns estados da máquina.
• Em certo sentido, as Máquinas de Turing esculpem a parte "finita" de todas as línguas, no sentido em que esculpem a parte que pode ser representada finitamente (por uma Máquina de Turing). Existem inúmeras línguas, mas muitas máquinas de Turing, por isso há um monte de coisas que nunca entenderemos porque é realmente infinito, em um infinito muito grande.
• A maioria dos problemas que podemos conceber não exige o poder de uma máquina de Turing. Muitos podem ser escritos usando recursão primitiva ou outros esquemas de recursão bem fundamentados. Portanto, a maioria dos algoritmos não exige o infinito das Máquinas de Turing.
• Para uma máquina de Turing que para, sempre há uma função que descreve a quantidade máxima de memória usada em relação ao tamanho da entrada. Portanto, não precisamos entender o infinito, simplesmente precisamos entender o relacionamento.

Um sistema fraco pode inventar um sistema mais forte?

A resposta aqui, eu acho, é sim, dependendo da sua definição. Por exemplo, a linguagem de todas as máquinas de Turing válidas pode ser descrita usando uma gramática livre de contexto, uma formalização computacionalmente mais fraca. Você pode até descrever uma linguagem comum que descreva a aparência de uma máquina de Turing válida e elas são finitas. (Alerta de spoiler, isso não diz muito, porque você pode mapear cada número inteiro em uma Máquina de Turing, portanto, o idioma normal$\{0,1\}^*$ pode ser o conjunto de todas as máquinas de Turing válidas).

E, é importante distinguir reconhecer uma coisa ou inventar uma descrição de algo e inventar todas as coisas. Podemos reconhecer o que é uma máquina de Turing, mas não podemos vê-los, e por causa de coisas como o problema da parada, certamente nem conseguimos entender todos eles.

Outras coisas infinitas

Essa questão não é diferente de perguntar como uma mente finita poderia entender os números naturais ou a função $y=x$ no $\mathbb{R}^2$. Ambos são infinitos, mas podem ser descritos de maneiras finitas.

Porém, existem funções, conjuntos e número real, tais como infinitos, que nunca podem ser descritos por nenhuma fórmula falada ou escrita possível (porque existem incontáveis ​​reais, mas inúmeras frases finitas em qualquer idioma humano). são mais teoremas verdadeiros do que provas, à la Gödel.

Assim, podemos descrever o infinito e falar de suas propriedades, talvez sem realmente entendê-lo, pelo menos sem entender todas as suas facetas.