Problema no ensino da computabilidade

22

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.

mcKlane
fonte
10
"Todas as funções que um computador pode calcular"? Normalmente, recorro a linguagens de programação, pois é provável que os alunos conheçam uma. Eu também tentei "qualquer receita para calcular uma função" como uma definição intuitiva de algoritmo.
Michaël Cadilhac
5
Um problema é computável se puder ser resolvido por um conjunto finito de regras que governam a evolução do sistema dinâmico discreto em um número finito de etapas.
Mohammad Al-Turkistany
1
Além disso, você pode usar o décimo problema de Hilbert para explicar aos alunos por que é insolúvel e que a prova de insolubilidade exigia, entre outras coisas, formalizar a noção de computabilidade em matemática.
Mohammad Al-Turkistany
Outra pergunta: A Tese de Church-Turing afirma que uma função pode ser calculada por alguma máquina de Turing se, e somente se, puder ser calculada por alguma máquina de qualquer outro modelo “razoável e geral” de computação [Goldreich, 2008]. Então, é concebível uma noção de computabilidade independente de modelo?
MS Dousti

Respostas:

37

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.

Andrej Bauer
fonte
2
Eu gosto bastante desse argumento, porque vai do concreto (o iPhone) ao abstrato.
Suresh Venkat
2
Aqui está um quebra-cabeça interessante: quais são os teoremas smn e utm em Haskell?
Andrej Bauer
18
"75 anos atrás, não havia computadores por perto." Isto é simplesmente falso. 75 anos atrás, havia muitos computadores ao redor. Eles eram humanos, principalmente mulheres; eles possuíam diplomas avançados de matemática, algumas ferramentas rudimentares de computação mecânica (como adicionar máquinas e regras de slides) e muito e muito papel. Esses computadores foram a espinha dorsal do Projeto Manhattan e do Bletchley Park durante a Segunda Guerra Mundial (não obstante a bomba e a bomba). Este é o ambiente de computação que Turing estava modelando: humanos com lápis e papel.
Jeffε
10
@ Jeff: Vamos lá, você sabe o que eu quis dizer.
Andrej Bauer
8
@ Jeff: podemos testar sua hipótese. Vá para seus colegas e peça que eles desenhem a imagem de "um computador usando uma saia curta". Por favor, informe quantos desenhou um ser humano.
Andrej Bauer
12

"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.

Peter Boothe
fonte
3
Nitpicking: o teorema de Abel-Ruffini afirma que não há solução algébrica geral - isto é, solução em radicais - para equações polinomiais de grau cinco ou superior. No entanto, existem métodos, como o radical Bring , para obter soluções em forma fechada das equações quânticas.
MS Dousti
Seu nitpicking está realmente correto. Ao discutir a computabilidade, você quer falar sobre coisas como "operações permitidas", e as soluções para os polinômios são uma daquelas coisas que ficam mais complexas quanto mais você olha para ela. Mas, para uma introdução, acho que as palavras "procedimento eficaz" e uma menção à fórmula quadrática são um excelente ponto de partida. Eles não estão totalmente corretos, mas a intuição é bastante correta, IMO.
quer
8

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".

Dave Clarke
fonte
6

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.

Kevin Wortman
fonte
0

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.

Vineet Kumar
fonte
A questão é sobre o ensino da computabilidade. Seria bom se você restringisse sua resposta ao material que respondesse a essa pergunta. Lembre-se de que o OP está ensinando estudantes de graduação, portanto, as opiniões pessoais (como as três últimas afirmações) podem não estar no escopo.
Vijay D