Problème d'enseignement de la calculabilité

22

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.

mcKlane
la source
10
"Chaque fonction qu'un ordinateur peut calculer"? Habituellement, j'ai recours à des langages de programmation, car les étudiants sont susceptibles d'en connaître un. J'ai également essayé de choisir "n'importe quelle recette pour calculer une fonction" comme définition intuitive de l'algorithme.
Michaël Cadilhac
5
Un problème est calculable s'il peut être résolu par un ensemble fini de règles qui régissent l'évolution d'un système dynamique discret en nombre fini d'étapes.
Mohammad Al-Turkistany
1
En outre, vous pouvez utiliser le dixième problème de Hilbert pour expliquer aux élèves pourquoi il est insoluble et que la preuve de l'insolvabilité exigeait, entre autres, de formaliser la notion de calculabilité en mathématiques.
Mohammad Al-Turkistany
Autre question: la thèse de Church-Turing déclare qu'une fonction peut être calculée par une machine de Turing si et seulement si elle peut être calculée par une machine de tout autre modèle de calcul «raisonnable et général» [Goldreich, 2008]. Alors, une notion de calcul indépendant du modèle est-elle concevable?
MS Dousti

Réponses:

37

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.

Andrej Bauer
la source
2
J'aime bien cet argument, car il va du concret (l'iPhone) à l'abstrait.
Suresh Venkat
2
Voici un puzzle intéressant: quels sont les théorèmes smn et utm dans Haskell?
Andrej Bauer
18
"Il y a 75 ans, il n'y avait pas d'ordinateurs autour." C'est tout simplement faux. Il y a 75 ans, il y avait BEAUCOUP d'ordinateurs autour. C'étaient des humains, principalement des femmes; ils avaient des diplômes avancés en mathématiques, quelques outils rudimentaires de calcul mécanique (comme l'ajout de machines et de règles de calcul), et beaucoup, beaucoup de papier. Ces ordinateurs ont été l'épine dorsale du projet Manhattan et du parc Bletchley pendant la Seconde Guerre mondiale (malgré la bombe et la Bombe). C'est l'environnement informatique que Turing modélisait: des humains avec un crayon et du papier.
Jeffε
10
@Jeffe: Allez, tu sais ce que je voulais dire.
Andrej Bauer
8
@JeffE: nous pouvons tester votre hypothèse. Allez voir vos collègues et demandez-leur de dessiner un "ordinateur portant une jupe courte". Veuillez indiquer combien de personnes ont attiré un être humain.
Andrej Bauer
12

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

Peter Boothe
la source
3
Nitpicking: le théorème d'Abel-Ruffini déclare qu'il n'y a pas de solution algébrique générale - c'est-à-dire une solution en radicaux - aux équations polynomiales de degré cinq ou plus. Cependant, il existe des méthodes, telles que le radical Bring , pour obtenir des solutions sous forme fermée d'équations quintiques.
MS Dousti
Votre piqûre est en fait juste. Lorsque vous discutez de calculabilité, vous voulez parler de choses comme les "opérations autorisées", et les solutions aux polynômes sont l'une de ces choses qui deviennent plus complexes à mesure que vous les examinez. Mais pour une introduction, je pense que les mots "procédure efficace" et une mention de la formule quadratique constituent un excellent point de départ. Ils ne sont pas tout à fait corrects, mais l'intuition est plutôt juste, OMI.
Peter Boothe
8

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

Dave Clarke
la source
6

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.

Kevin Wortman
la source
0

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.

vigne kumar
la source
La question porte sur l'enseignement de la calculabilité. Ce serait bien si vous limitez votre réponse au matériel répondant à cette question. Gardez à l'esprit que le PO enseigne aux étudiants de premier cycle, de sorte que les opinions personnelles (telles que vos trois dernières déclarations) peuvent ne pas être de portée.
Vijay D