Problema no ensino da computabilidade

Tenho dificuldade em ensinar o conceito de funções computáveis. Tentei desenvolver a idéia de por que pesquisadores como Hilbert / Ackermann / Godel / Turing / Church / ... inventaram a noção de 'computabilidade'. Os alunos imediatamente perguntaram: "o que significa computabilidade?" e não posso responder a menos que eu as ensine máquinas de Turing e depois responda "uma função é computável se uma máquina de Turing a computar".

Tão,

Existe uma descrição da computabilidade que não exija o recurso a máquinas de Turing, cálculo λ ou modelos similares de computação? Mesmo uma descrição intuitiva será suficiente.

75 anos atrás, não havia computadores por perto. Portanto, era preciso explicar com muito cuidado a idéia matemática de um computador.

Hoje todo mundo sabe o que é um computador e provavelmente carrega um na maioria das vezes. Isso pode ser usado com muito êxito no ensino, porque você pode pular a idéia bastante desatualizada de uma máquina com uma fita. Quero dizer, quem usa uma fita? (Eu sei, eu sei, você se sente insultado e Turing era um grande homem e tudo isso, e eu concordo com você).

Você apenas entra na sala e pergunta: para que haja algo que seus iPhones não possam computar? Isso coloca você imediatamente em perguntas sobre recursos limitados. Então você diz: bem, suponha que sua máquina tenha memória ilimitada, existe algo que não possa ser computado? E você idealiza um pouco mais e limita a atenção às funções teóricas dos números (porque você não está interessado no Facebook no momento). Você terá que explicar um pouco como os computadores funcionam (como mencionado nos comentários, é bom que os alunos conheçam uma linguagem de programação porque você pode usá-la em vez de descrever o hardware), mas depois disso você pode usar todos os argumentos clássicos de computabilidade teoria para obter resultados. Não importa que a imagem mental de uma máquina de seus alunos seja o iPhone. De fato, importa:mais relevante para eles saberem que o iPhone não pode fazer certas coisas.

"Uma função é computável se houver um 'procedimento eficaz' para ir da entrada à saída". Ao introduzir este tópico, apontei no passado como eles (os alunos) têm um procedimento eficaz para resolver equações quadráticas, mas não um para resolver equações de grau 5 ou mais. Isso pode levar a uma discussão de como alguém pode formalizar um 'procedimento eficaz', mas essa discussão é algo que você deseja que aconteça, por isso acho que isso é um recurso, e não um bug.

Talvez o ponto seja que todos esses modelos tenham como objetivo capturar qual é a noção de computabilidade. O fato de todos serem equivalentes significa que a noção que eles estão tentando capturar é robusta. Portanto, embora isso não escape ao seu dilema, essa robustez dá credibilidade à noção de que "uma função é computável se houver uma máquina de Turing que a computa".

Começo perguntando "existe alguma pergunta que nenhum computador possa responder de forma convincente?" e conduza a discussão a questões filosóficas como "se uma árvore cai na floresta, ela soa?" ou "existe uma vida após a morte?" Nós rapidamente obtemos um consenso de que a linguagem humana pode expressar perguntas de sim / não envolvendo paradoxos ou conceitos que não podem ser expressos matematicamente e, portanto, sim, há perguntas não computáveis.

Depois, pergunto retoricamente se existem perguntas não computáveis ​​sobre conceitos que podem ser representados em um computador, por exemplo, números inteiros e gráficos. Eu digo que sim, um exemplo é o famoso problema de parada, que consiste em examinar uma descrição de um programa e dizer se ele possui loops infinitos. Intuitivamente, verifica-se que os loops infinitos são como buracos negros, e qualquer programa que observe um loop infinito pode ficar preso no próprio loop infinito. Portanto, qualquer procedimento que responda a esse problema pode durar para sempre; portanto, pela definição de "algoritmo", nenhum algoritmo pode responder ao problema de parada.

Depois, volto a fazer provas nas máquinas de Turing.

Bem, uma função é computável se aceitar entradas formadas ou geradas por um padrão específico. Um padrão específico significa que todas as entradas devem ter uma relação, uma entrada específica pode ser gerada por ela, entrada anterior ou próxima. Se as entradas não tiverem esse tipo de sequência, não há possibilidade de desenvolver um modelo ou função que possa aceitar. Mais uma coisa que quero dizer é que existe uma diferença básica entre uma máquina e um ser humano. Uma máquina não pôde ser formada para entradas não sequenciais, mas os humanos são. Além disso, essa é uma grande interrupção na criação de robôs que se comportam em humanos.