Salut tout le monde ! Alors voilà, pour les cours je dois faire un papier sur un sujet choisi, j'ai voulu prendre quelque chose qui sortait de l'ordinaire et qui était intéressant à mes yeux, donc j'ai opté pour la machine de Turing, là pour l'instant je suis dans une phase de collectes d'informations à droite et à gauche sur le web, mais j'aimerais savoir si certains d'entre vous ici ont quelque chose à ajouter, un fait à partager ou autre information qui pourrait m'être utile sur le sujet histoire de compléter les sources dont je dispose actuellement (web et je viens de commander un bouquin qui je l'espère vulgarisera un peu la chose parce que si c'est que des formules de math ça va être compliqué)

D'avance merci pour votre temps

Je sais pas ce qu'on peut t'apporter de plus que ce qu'il y a sur Internet.

Il y a des choses que tu veux savoir en particulier ? Si tu avais des questions ça serait plus facile.

Je sais pas ce qu'on peut t'apporter de plus que ce qu'il y a sur Internet.

Il y a des choses que tu veux savoir en particulier ? Si tu avais des questions ça serait plus facile.

Je sais pas à quel niveau d'étude t'es donc désolé si ce que je dis est trivial pour toi

Tu peux présenter les "limites" des machines de Turing en tant que reconnaisseurs , du genre tu peux faire la démonstration qu'il y a des langages qu'une machine de Turing ne peut pas reconnaître

Il faudrait que tu nous dises plus exactement ton niveau d'études, dans quel cadre tu dois faire ça, combien de temps tu as pour faire ta présentation / quelle taille doit faire ton exposé.

Des sujets que tu peux aborder :
- La thèse de Church-Turing
- D'autres modèles de calcul qui sont turing-complets : le lambda-calcul, les fonctions récursives
- La preuve d'indécidabilité du problème de l'arrêt (c'est une preuve assez élégante, courte, et qui demande peu de notions mathématiques)
- La théorie de la complexité et le problème P=NP