A tese de Church-Turing também se aplica à inteligência artificial?

Pela tese de Church-Turing, é impossível projetar um algoritmo para decidir o problema da parada.

A palavra algoritmo, neste contexto, inclui inteligência artificial ou não, isto é, a tese de Church-Turing também se aplica à inteligência artificial?

É possível projetar um sistema de inteligência no futuro para resolver esse problema ou, pela tese de Church-Turing, nenhuma IA também será capaz de decidir o problema de parada?

computability artificial-intelligence halting-problem church-turing-thesis M ama D
fonte

É improvável que um sistema de IA possa decidir qualquer coisa (no sentido formal, determinístico), mas se pudesse, certamente violaria a tese de Church-Turing ou a indecidibilidade do problema de Halting. (Este último se é escrita em uma linguagem Turing-complete, o ex contrário.)

Raphael

Por que você acha possível que a inteligência artificial não seja coberta (ou preocupada) pela tese de Charch-Turing?

23815 babou

@babou porque inclui não determinismo, aprendizado, etc. Existem problemas não solucionáveis que a IA nos fornece muito boa aproximação da solução.

M AMA D

@ Drupalist: mas a decidibilidade de algum problema significa apenas que existe um algoritmo tal que, para qualquer entrada do espaço de entrada do problema, a saída correta seja produzida. Portanto, sim, um algoritmo de IA (ou qualquer outro algoritmo) pode fornecer boas aproximações para o problema de parada, mas isso não implica em capacidade de decisão.

Roy O.

Respostas:

A tese de Church-Turing diz que a noção informal de um algoritmo como uma sequência de instruções coincide com as máquinas de Turing. Equivalentemente, diz que qualquer modelo razoável de computação tem o mesmo poder que as máquinas de Turing.

Uma inteligência artificial é um programa de computador, ou seja, um algoritmo. Se a tese de Church-Turing for válida, você poderá implementar esse algoritmo em uma máquina de Turing. Como as máquinas de Turing não podem decidir seu próprio problema de parada, segue-se que, sob a tese de Church-Turing, as inteligências artificiais não podem decidir o problema de parada das máquinas de Turing.

David Richerby
fonte

Por outro lado, se a IA foi escrita em algum tipo de computador analógico ou circuito infinito não uniforme, então o problema da parada para máquinas de Turing está de volta ao quadro.

DanielV

@DanielV Um circuito infinito não uniforme não ajuda. Se tiver uma descrição computável, não poderá resolver o problema da parada; se não tiver uma descrição computável, você não poderá construí-la.

David Richerby

Você não pode construí-lo com uma máquina de Turing. Isso não significa que não significa que sua existência seja mais paradoxal do que 2 pontos, sendo uma distância arbitrária.

DanielV

@DanielV Como você vai dizer ao seu eletricista quais portões colocar no

n

$n$ th circuito se não houver descrição computável?

David Richerby

@DanielV Existem alguns problemas que você simplesmente não pode calcular. Você precisa decidir quando resolveu o problema, bem como qual é a resposta. No caso do problema de parada, não há como determinar se você resolveu o problema, muito menos descobrir qual é a resposta.

mais claro