Problème d'enseignement de la calculabilité

J'ai du mal à enseigner le concept de fonctions calculables. J'ai essayé de développer l'idée de pourquoi des chercheurs comme Hilbert / Ackermann / Godel / Turing / Church / ... ont inventé la notion de «calculabilité». Les étudiants ont immédiatement demandé: "que signifie la calculabilité?" et je ne peux pas répondre à moins de leur enseigner les machines de Turing, puis de répondre "une fonction est calculable si une machine de Turing la calcule".

Alors,

Existe-t-il une description de la calculabilité qui ne nécessite pas le recours à des machines de Turing, au λ-calcul ou à des modèles de calcul similaires? Même une description intuitive suffira.

Il y a 75 ans, il n'y avait pas d'ordinateurs autour. Il fallait donc expliquer très soigneusement l' idée mathématique d'un ordinateur.

Aujourd'hui, tout le monde sait ce qu'est un ordinateur et en transporte probablement un la plupart du temps. Cela peut être utilisé avec beaucoup de succès dans l'enseignement, car vous pouvez ignorer l'idée plutôt obsolète d'une machine avec une bande. Je veux dire, qui utilise une bande? (Je sais, je sais, tu te sens insulté et Turing était un grand homme et tout ça, et je suis d'accord avec toi).

Il vous suffit d'entrer dans la classe et de demander: donc y a-t-il quelque chose que vos iPhones ne peuvent pas calculer? Cela vous amène immédiatement à des questions sur les ressources limitées. Ensuite, vous dites: supposons que votre machine ait effectivement une mémoire illimitée, y a-t-il quelque chose qu'elle ne peut pas calculer? Et vous idéalisez un peu plus et limitez votre attention aux fonctions de théorie des nombres (parce que Facebook ne vous intéresse pas pour le moment). Vous devrez expliquer un peu comment les ordinateurs fonctionnent (comme mentionné dans les commentaires, c'est bien si les étudiants connaissent un langage de programmation parce que vous pouvez l'utiliser au lieu de décrire le matériel), mais après cela, vous pouvez utiliser tous les arguments classiques de calculabilité théorie pour obtenir des résultats. Peu importe que l'image mentale d'une machine par vos élèves soit iPhone. En fait, cela compte:plus pertinent pour eux de savoir que leur iPhone ne peut pas faire certaines choses.

"Une fonction est calculable s'il existe une" procédure efficace "pour passer de l'entrée à la sortie." Lors de l'introduction de ce sujet, j'ai indiqué dans le passé comment ils (les élèves) ont une procédure efficace pour résoudre des équations quadratiques, mais n'en ont pas pour résoudre des équations de degré 5 ou plus. Cela peut enchaîner dans une discussion sur la façon de formaliser une «procédure efficace», mais cette discussion est quelque chose que vous souhaitez avoir, donc je pense que c'est une fonctionnalité plutôt qu'un bug.

Peut-être que le fait est que tous ces modèles visaient à saisir ce qu'est la notion de calculabilité. Le fait que tous soient équivalents signifie que la notion qu'ils tentent de saisir est solide. Ainsi, bien que cela n'échappe pas à votre dilemme, cette robustesse donne du crédit à la notion selon laquelle "une fonction est calculable s'il existe une machine de Turing qui la calcule".

Je commence par demander "y a-t-il une question à laquelle aucun ordinateur ne pourra jamais répondre de manière convaincante?" et mener la discussion vers des questions philosophiques telles que "si un arbre tombe dans la forêt, est-ce que ça fait du bruit?" ou "y a-t-il une vie après la mort?" Nous obtenons rapidement un consensus sur le fait que le langage humain peut exprimer des questions oui / non impliquant des paradoxes ou des concepts qui ne peuvent pas être exprimés mathématiquement, et donc, oui, il y a des questions non calculables.

Ensuite, je demande rhétoriquement s'il y a des questions non calculables sur les concepts qui peuvent être représentés dans un ordinateur, par exemple des nombres entiers et des graphiques. Je dis que oui, un exemple est le fameux problème d'arrêt, qui consiste à examiner une description d'un programme et à dire s'il a des boucles infinies. Intuitivement, il s'avère que les boucles infinies sont comme des trous noirs, et tout programme qui observe une boucle infinie pourrait être piégé dans une boucle infinie elle-même. Donc, toute procédure qui répond à ce problème peut s'exécuter indéfiniment, donc par la définition d '"algorithme", aucun algorithme ne peut répondre au problème d'arrêt.

Puis je replonge dans les épreuves sur les machines Turing.

Eh bien, une fonction est calculable si elle accepte des entrées formées ou générées par un modèle spécifique. Un modèle spécifique signifie que toutes les entrées doivent avoir une relation, une entrée particulière peut être générée par son entrée précédente ou suivante. Si les entrées n'ont pas ce type de séquence, il n'y a aucune possibilité de développer un modèle ou une fonction qui puisse accepter. Une chose de plus que je veux dire, c'est qu'il y a une différence fondamentale entre une machine et un être humain. Une machine n'a pas pu être formée pour des entrées non séquentielles, mais les humains le sont. C'est aussi une grosse interruption de la fabrication de robots qui se comportent réellement.