Poder da computação humana: os humanos podem decidir o problema da parada nas máquinas de Turing?

Sabemos que o problema da parada (nas máquinas de Turing) é indecidível para as máquinas de Turing. Existe alguma pesquisa sobre até que ponto a mente humana pode lidar com esse problema, possivelmente auxiliada por máquinas de Turing ou computadores de uso geral?

Nota : Obviamente, no sentido mais estrito, você sempre pode dizer não, porque existem Máquinas de Turing tão grandes que nem podiam ser lidas na vida útil de um único humano. Mas essa é uma restrição sem sentido que não contribui para a questão real. Então, para acalmar as coisas, teríamos que assumir humanos com um tempo de vida arbitrário.

Assim, poderíamos perguntar: Dada uma máquina de Turing T representada de qualquer maneira adequada, um H humano arbitrariamente de vida longa e uma quantidade arbitrária de buffer (ou seja, papel + canetas), H pode decidir se T pára na palavra vazia?

Corolário: Se a resposta for afirmativa, isso também não seria resolvido se algum computador tivesse chance de passar no teste de turing?

É muito difícil definir uma mente humana com um rigor matemático, pois é possível definir uma máquina de Turing. Ainda não temos um modelo de funcionamento do cérebro de um mouse, no entanto, temos o hardware capaz de simulá-lo. Um rato possui cerca de 4 milhões de neurônios no córtex cerebral. Um ser humano tem 80-120 bilhões de neurônios (19-23 bilhões de neocorticais). Assim, você pode imaginar quanto mais pesquisas serão necessárias para obter um modelo de funcionamento da mente humana.

Você poderia argumentar que precisamos apenas fazer uma abordagem de cima para baixo e não precisamos entender o funcionamento individual de cada neurônio. Nesse caso, você pode estudar alguma lógica não monotônica, raciocínio abdutivo, teoria da decisão, etc. Quando surgem as novas teorias, ocorrem mais exceções e paradoxos. E parece que não estamos nem perto de um modelo funcional de uma mente humana.

Depois de fazer o cálculo proposicional e depois o predicado, perguntei ao meu professor de lógica:
"Existe alguma lógica que possa definir todo o conjunto da linguagem humana?"
Ele disse:
"Como você definiria o seguinte?
Para ver um mundo em um grão de areia
e um céu em uma flor selvagem,
segure o infinito na palma da sua mão
e a eternidade em uma hora.
Se você conseguir, poderá tornar-se famoso."

Houve debates que uma mente humana pode ser equivalente a uma máquina de Turing. No entanto, um resultado mais interessante seria que a mente humana não fosse equivalente a Turing, que daria origem a uma definição de um algoritmo que não é possivelmente computável por uma máquina de Turing. Então a tese da Igreja não se sustentaria e poderia haver um algoritmo geral que pudesse resolver um problema de parada.

Até entendermos mais, você poderá encontrar algumas idéias em um ramo da filosofia. No entanto, nenhuma resposta para sua pergunta é geralmente aceita.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

Acho que não há como dar uma resposta definitiva a essa pergunta, pois ninguém realmente conhece as capacidades da mente humana (e duvido que alguém o faça).

Mas há uma visão que fornece uma possível solução ou explicação para essa pergunta:

Quando procuramos um oráculo para resolver o problema de parada (ou decidimos a provabilidade de fórmulas lógicas de primeira ordem, etc.), naturalmente queremos que o oráculo esteja correto , não deve cometer erros. Mas a mente humana não é consistente, comete erros. Ninguém pode dizer honestamente que todas as declarações que ele acredita serem verdadeiras são realmente verdadeiras. Essa inconsistência pode ser vista como a fonte do poder que a mente humana possui. Devido à sua inconsistência, não está sujeito a limitações decorrentes do problema de parada, o teorema da incompletude de Gödel etc. Cometemos erros, acreditamos erroneamente em declarações falsas e, à medida que nosso conhecimento cresce, as corrigimos (e, é claro, descobrimos novas declarações falsas em que acreditamos). Por outro lado, queremos que todas as formalizações da noção de algoritmo ou todos os cálculos lógicos sejam consistentes, para que possamos provar de uma vez por todas que estão livres de tais erros. E isso os torna limitados.

Apenas para esclarecer: a hipótese de Church-Turing não tem nada a ver com algum dogma de uma hipotética Igreja de Turing. Não há nada religioso nisso. Pelo contrário, é apenas uma hipótese que resume o melhor de nosso conhecimento. Não há implicação metafísica. A questão de se os seres humanos poderiam fazer melhor, de que poderiam alcançar mais do que máquinas, é uma questão metafísica, pois não temos estritamente nenhum controle sobre ela, nenhuma sugestão do que poderia diferenciar um humano de uma máquina. Portanto, essa pergunta deve ser migrada para metaphysics.stackexchange.com.

Mas vamos supor que o cérebro humano possa resolver o problema de parada da máquina de Turing. Então o modelo computacional das Máquinas de Turing se torna muito menos importante, e a Hipótese de Church-Turing se torna muito menos relevante, pois temos um modelo mais poderoso chamado Modelo Humano (para evitar a palavra máquina ). É claro que esse modelo humano (de vida arbitrária) vem com sua própria hipótese sobre computabilidade.

Mas então, enquanto o problema de parada das máquinas de Turing não é mais crítico, agora temos que lidar com o problema da parada do modelo humano. E a diagonalização mostrará que o problema da parada do modelo humano não é decidível por um humano. Então o que?

Agora, você pode objetar que a diagonalização não seria aplicável. Acho que isso significaria que associar alguma forma de numeração de Gödel a dispositivos de computação, provas ou o que quer que descrevemos com notação não seria mais possível, embora atualmente seja a base de toda a ciência. Em outras palavras, teríamos que lidar com entidades, conceitos que não têm representação escrita, que não podem ter uma representação escrita ou, de maneira mais geral, conceitos sem uma representação sintática, seja ela escrita, oral ou não.

Certamente, isso estaria em oposição ao ensino de João, cuja primeira frase é: " No princípio era o Verbo, e o Verbo estava com Deus, e o Verbo era Deus " . Negando a importância fundamental da sintaxe, da palavra, é, portanto, uma afirmação muito anticristã. É claro que não estou adotando uma posição sobre isso, mas desde que minha primeira opinião sobre essa questão é que ela é metafísica e, como a pergunta não está em espera, parece natural considerar todas as consequências, inclusive as consequências metafísicas.

Considere isso de uma perspectiva diferente.

• A lógica de primeira ordem é indecidível, ou seja, não existe procedimento de decisão que determine se as fórmulas arbitrárias são logicamente válidas. (Mas o conjunto de verdadeiras fórmulas de primeira ordem é semi-decidível , ou seja, se uma fórmula for verdadeira, é possível encontrar uma prova por um algoritmo.)
• Assistentes de prova ajudam a provar teoremas na lógica de primeira ordem (ou mesmo superior). O assistente de prova garante que a prova seja feita corretamente e pode até ajudar a resolver alguns casos. No entanto, a interação humana é necessária para orientar o assistente de prova para a resposta correta.

Assistentes de prova podem ser usados ​​para provar propriedades de máquinas de Turing individuais.

O comentário de Carl Mummert acertou em cheio.

1. Meu entendimento (corrija-me se estiver errado) da tese de Church-Turing é a ideia de que qualquer coisa que possa ser calculada pode ser calculada por uma máquina de Turing.

2. E também, se uma Máquina de Turing pudesse calcular se outra Máquina de Turing iria parar ou não em uma entrada (problema de parada), também seria possível calcular se outra Máquina de Turing não pararia em uma determinada entrada (apenas troque sim por não e não para sim!) - significativo, porque então você poderia alimentar esta máquina de Turing sozinha - ela não se detinha na entrada? Se sim (não está parando), então não (está parando ??). Se não, então sim. Se sim, então não. Se não, então você ... hmmm.

Então, 2. mostra que é impossível para uma máquina de Turing resolver o problema de parada. Mas não acho que exista uma evidência clara de contradizer 1. neste momento. Todo modelo de computação conhecido ainda pode resolver (decidir) o máximo que uma máquina de Turing.

O ônus da prova parece estar na pessoa que está apresentando um novo modelo de computação, que tem mais poder (isto é, pode decidir mais problemas) do que a clássica máquina de Turing.

A propósito, algumas ótimas palestras sobre isso podem ser encontradas aqui .

Não há evidências de que o cérebro humano seja de fato algo mais que uma máquina de Turing. De fato, parece que todo o universo pode ser simulado em uma máquina de Turing (suficientemente grande).

Os seres humanos são "inteligentes" por causa de algoritmos inteligentes escritos de maneira inteligente em neurônios, para que os cientistas da computação não possam roubá-los ou implementá-los com eficiência. Por mais inteligentes que sejam esses algoritmos, eles provavelmente não podem resolver de maneira confiável o problema de parada.

Em resumo: NÃO

existem máquinas de Turing para as quais ainda não sabemos se essas máquinas param ( conjectura de Collatz, por exemplo).

Até encontrarmos uma maneira de enumerar todas as Máquinas de Turing para as quais não temos uma prova de parada, e até não encontrarmos uma maneira de provar a Haltness dessas máquinas, não somos melhores que uma máquina de Turing (se Estou certo de que alguém já provou que não podemos provar tudo, um ponto em relação ao fato de sermos tão limitados quanto as Máquinas de Turing). Oh, espere, não podemos enumerar todas essas máquinas porque, de fato, temos uma memória limitada e uma vida útil limitada.

No entanto, você pergunta, é auto-resposta:

Você está perguntando se o ser humano é capaz de "decidir", mas a decisão em si é definida como um algoritmo, ou então executamos um algoritmo em nossas mentes e chegamos a uma conclusão correta (ou nenhuma conclusão: problemas em aberto), ou nós apenas fazemos um palpite.

A teoria da computação é sobre:

• Suponha que exista um algoritmo de caixa preta (Oracle) que possa responder sim ou não a determinadas perguntas
• Em seguida, você pode usá-lo para responder perguntas não respondidas criando outro algoritmo que o usa
• Ao fazer isso, você termina com uma contradição

Isso significa que, desde que você tenha qualquer sistema que queira uma resposta Noou Yesresposta, o Oracle não é compatível com esse sistema; portanto , o Oracles pode realmente existir, mas não temos como comunicar seus resultados , porque, se pudermos comunicar seus resultados, acabamos com uma contradição em algum lugar.

Suponha que a mecânica quântica seja feita de muitos oráculos pequenos, então você não poderá comunicar os resultados deles porque, ao ler o status de uma partícula, você também altera o status dessa partícula.

Eu tive a resposta, mas já li ..

De fato, podemos provar qualquer coisa se começarmos pela hipotese falsa. Assim, podemos provam que uma parada algoritmo, mas também podemos provam que um algoritmo não parar, que pode ser interessante, mas é inútil já que uma contraditória (você quer um Yesou Noresponder) resultado não é o que você quer.

como na resposta dos DCs (e para expandir um pouco), existe um forte senso de que essa questão (combinação de humanos e computadores na busca de soluções de casos especiais para o problema de parada) está relacionada ao campo do ATP, prova de teoremas automatizados e as provas assistidas por computador intimamente relacionadas . também se sabe há muito tempo que existe uma forte correspondência entre programas e provas na correspondência de Curry-Howard . também relacionado / similar a isso está provando o encerramento do programa (por exemplo, através de invariantes de loop ou variantes de loop ). de fato, existe um sentido profundo em que todosda matemática é sobre esse problema, porque praticamente todas as declarações matemáticas podem ser convertidas em perguntas sobre programas específicos sobre interrupções ou não de TMs. veja, por exemplo, [2] para mais informações e muitas outras referências sobre ATP etc.

[1] é um livro semi-famoso sobre o assunto que examina a questão em detalhes, relacionando-a com a possibilidade de inteligência artificial. brevemente, a idéia de Penrose é que a verdadeira IA deve ser impossível, porque os seres humanos podem apresentar provas de indecidibilidade, como Turings, impedindo o problema ou a prova da incompletude de Godel, enquanto os computadores não podem devido aos mesmos fenômenos.

[1] Nova mente de imperadores por Penrose

[2] aventuras e promoções em ATM , vzn

Sistemas modernos de supercomputadores certamente podem simular o comportamento de pelo menos um átomo. Se átomos individuais podem ser simulados, também é possível simular a mente humana, criando um sistema de computador grande o suficiente para a simulação dos átomos individuais. No entanto, acho que isso por si só não seria suficiente. Você também precisaria de uma fonte de entropia para obter números aleatórios verdadeiros para a simulação da mente humana. A melhor fonte de entropia provavelmente seria o decaimento radioativo ou algo assim. O que isto significa?

Eu acho que a mente humana é mais poderosa do que uma máquina de Turing, porque uma MT é determinística. Você não pode simular a aleatoriedade verdadeira em uma máquina de Turing. (Pelo menos essa é a impressão que recebi da discussão a seguir

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

) No entanto, penso que uma máquina de Turing, ligada a uma verdadeira fonte de entropia, seria capaz de simular uma mente humana.

Se também se leva em conta a aleatoriedade do ambiente, que interage com a mente humana (por exemplo, a comida, a comida, como o sono, a caminhada, basicamente, vivemos nossas vidas), então certamente acho que uma MT com entropia é necessária para a simulação da mente humana. Não se esqueça que a mente humana também é constantemente exposta à radiação de fundo, que também pode interagir de forma imprevisível com as moléculas do cérebro. Mas acho que, mesmo se considerarmos um ambiente completamente "isolado" (isso é possível? Porque o seguinte parece indicar que talvez não seja possível: http://hps.org/publicinformation/ate/faqs/faqradbods.html) - basicamente um "cérebro no pote" -, você provavelmente ainda obteria processos verdadeiramente aleatórios, que ocorreriam em algum lugar do cérebro humano. Tenho certeza de que um biólogo poderia resolver essa parte da questão? Além disso, não esqueça que um ser humano também faz parte de seu ambiente:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

Talvez algumas dessas bactérias também influenciem o funcionamento interno do cérebro humano de alguma maneira e a composição dessas bactérias possa mudar durante a vida de um ser humano (também dentro de certos limites, suponho?). A questão é se o comportamento dessas bactérias é aleatório dentro de certos limites. Se pelo menos um processo dentro de pelo menos um desses organismos é verdadeiramente aleatório e também afeta de alguma forma indiretamente o cérebro humano, seria necessário um TM com uma fonte de entropia para simular a mente humana.

Então, para responder à pergunta original:

Um "humano" (como definido na pergunta) pode resolver o problema da parada? Sim, se for o problema de parada para todas as TMs determinísticas e não se for para todas as TMs, anexado a uma fonte de entropia.

Todo pensamento humano confunde problemas únicos em experiência pessoal. Podemos nos convencer de que resolvemos adequadamente um problema o suficiente para interromper, mas nunca sabemos ao certo no sentido algorítmico que um computador iria adquirir uma solução. Fique quieto e observe sua própria mente. 99,9% das mensagens que acontecem em nosso circuito neural não têm nada a ver com uma representação lógica do mundo. Em vez disso, estamos lidando com sentimentos "instintivos", dados sensoriais e uma enxurrada de memórias, associações e atitudes que variam constantemente. É por isso que temos método científico.