Discussion:Machine de Turing

Définitions (Discussion de 2006)

Bonjour! Je connais pas grd chose à l'informatik, mais je lis dans Manuel de Landa (1991) qu'une "vraie machine de Turing", soit dans l'état abstrait dans lequel elle existait entre 1936 et 1950, soit dans sa forme présente, le PC, peut être défini comme "machine universelle", c'est-à-dire "une machine qui peut simuler les travaux de n'importe quelle autre machine. Cela, bien sûr, ne veut pas dire qu'une machine de Turing peut simuler des réfrigérateurs, des automobiles ou des grilles-pains. Plutôt, elle peut reproduire le comportement de n'importe quel machine qui opère avec des "symboles", ou des inscriptions physiques de quelque sorte que ce soit: machines à écrire, calculateurs, "piannolas" [je présume que ça veut dire: "synthétiseurs"] (...) Un processeur Word est simplement un programme informatique simulant le fonctionnement d'une machine à écrire" (p.129-130). Cette description me paraît particulièrement saisissante et explicative pour le novice que je suis, en particulier la dernière phrase expliquant qu'une machine de Turing, par exemple un processeur Word, simule une machine de symboles, c'est-à-dire/par exemple une machine à écrire, une calculette ou un synthé"... Je pense que ça serait une bonne idée de la reprendre dans l'article, en intro; je ne le fais pas moi-même n'étant pas très compétent, mais ça le mérite d'éclaircir ce qui reste pour nous autres des arcanes obscures... Ahbon? 8 mai 2006 à 19:13 (CEST)

Je ne suis pas sûr que cette idée soit forcément bonne. Il ne faut pas faire l'amalgame entre machine de Turing, qui est un outil abstrait utile à l'infomatique théorique et à la compréhension d'algorithme et de machines, avec les choses qui sont Turing-completes.

Justement, quelque part tu fais toi-même l'amalgame. Ton PC n'est pas une machine de Turing, mais est Turing-complet. Il ne faut pas non plus se mélanger avec le terme de machine universelle, qui dans le cadre des machines de Turing est une machine de Turing capable de simuler le fonctionnement de toute autre machine de Turing (et non pas n'importe quelle machine). C'est la thèse Church-Turing qui permet de dire que les machines de Turing peuvent simuler tout ce qui est mécaniquement réalisable. Le fait qu'un ordinateur soit Turing-complet n'en découle pas forcément à mon avis, et peut se montrer indépendemment.

Il n'est pas de mon intention de me moquer d'une quelconque ignorance. Mais je trouve la phrase d'introduction "Une machine de Turing est un modèle abstrait du fonctionnement d'un ordinateur et de sa mémoire" déjà assez informative et fausse (la machine de Turing ayant été créée avant l'ordinateur, elle n'a pas pu être faite pour simuler celui-ci.) Je vais d'ailleurs modifier cette introduction pour coller plus à la réalité.DainDwarf 13 juillet 2006 à 15:10 (CEST)

De toute façon le modèle de machine de Turing décrit ici, si je ne me trompe, n'est pas celui de Turing, mais celui de Kleene, proposé dans les années 50, donc après l'invention de l'ordinateur. Pierre de Lyon 9 avril 2007 à 14:40 (CEST)

L'exemple est mal expliqué

Je ne pense pas être totalement bête mais, au bout d'un quart d'heure, je n'arrive toujours pas à comprendre l'exemple. A la deuxième ligne, je suis déjà perdu : "Puis elle utilise l’état e2 pour se déplacer vers la droite, en sautant les 1, et le premier 0 qu’elle rencontre. " On nous explique, au début, que le ruban lu contient une succession de 1. Quel est ce premier 0?

Même la définition n'est pas claire je trouve. Il est difficile de comprendre comment les informations entre et sortent de la machine. On dirait qu'un seul ruban sert au deux?!

Si savez ce qu'est une machine de Turing, merci beaucoup d'améliorer cet article. --Emmanuel Laude (d) 16 août 2008 à 11:53 (CEST)

probleme de définition

je n'ai aucun bon site sous l main a vous proposer par contre je connais pour l'avoir étudiée la description de la fameuse "machine de turing" (j'ai eu sous les yeux sa thèse et ses shémas): elle est une idéalité, notamment parce qu'elle présuppose un ruban infini, deux fois, en amont et en aval du traitement. Lorsque les inventeurs de l'ordinatique veulent faire des machines de turing, turing leur dit: 1. c'est impossible a faire (idéalité)2. si vous le faites votre ruban n'est pas infini, donc si vous voulez parler de "machine de turing", c'est bien un dérivé applicable de mon invention, mais précisez "machine de Turing LIMITEE (ou "impafaite")"!!!! 3. il avoue a ses amis que même sa machine n'est pas intelligente, qu'elle est une idéalité d'une forme de l'intelligence, mais que la machine "limitée" elle, elle ne peut en aucun cas etre intelligente. Tout le paradoxe c'est que juste apres avoir dit ca il defend l'"intelligence artificielle" comme rendue possible par l'ordinatique et propose de nombreuses objections à ceux qui prétendent qu'une machine ne peut penser, pour aller encore plus loin il propose le test connu comme "Test de Turing" qui est une blague admirable, puisque avec ca un humain peut être considéré selon les informations qu'il fourni comme "dénué d'intelligence" et l'"ordinateur" (dont les premices existent péniblement juste en labo) peut être déclaré "intelligent"... (voir à ce sujet Lucien SFEZ "Critique de la Communication", sur tous les points concernant Turing, tout y est sauf le shémas, au Seuil, Paris, réédition 1991) Loïc M.L.

loicml@yahoo.fr

nota: quand au livre signalé, c'est juste une compilation traduite de deux textes de Turing qui ne parlent que de sous-sujets connexes mais ne prétendent jamais décrire la "Machine de Turing", et mettre Alan Turing comme "auteur" est quelque peu douteux (publié 40 an après sa mort sous un titre qu'il n'a jamais voulu et avec ce contenu???)Il existe une version de la thèse de Turing (en anglais) à la "Library of Congress", et des copies de pages traduites ou non circulent...ref: "Extracted from the Proceedings of the London mathematical society, ser. 2, vol. 45, 1939." Thesis (Ph. D.)--Princeton university, 1938.

Bonjour. Sur la bibliographie : le livre cité contient la traduction de deux articles d'Alan Turing, publiés de son vivant dans Proceedings of the London Mathematical Society pour l'un et dans Mind pour le second, et dont la paternité n'a (à ma connaissance) jamais été contestée. L'article sur la machine de Turing, On Computable Numbers... est considéré comme l'article séminal présentant la machine de Turing et la MT universelle (que Turing ne nomme pas lui-même « machine de Turing » mais computing machine). J'ai également référencé l'article original en anglais. C'est une référence fondamentale, parfaitement acceptable et figurant dans la bibliographie de tout bon cours de calculabilité/complexité. La thèse de Turing est également une source intéressante, mais je n'ai pas la référence complète, l'avez-vous ? (J'ai mis en commentaire la référence partielle que vous avez introduite). Pour information :

• L'article est antérieur à la thèse ;
• L'article introduit la MT déterministe, la thèse présente en sus l'extension non-déterministe (sauf erreur de ma part) ;
• Le ruban infini des deux côtés est une facilité de notation qui n'apporte aucune expressivité supplémentaire par rapport au ruban infini d'un seul côté ;
• La MT est bien un modèle de calcul théorique, personne ne le conteste.

Pour le reste, vous êtes bien libre d'exprimer votre opinion et votre compréhension des problèmes traités dans la page de discussion, mais attention à ne pas mélanger article encyclopédique et page de discussion (j'ai vu que vous aviez retiré les remarques correspondantes). Cordialement, - Eusebius ^[causons] 3 octobre 2008 à 19:21 (CEST)

CN (comme Turing l'appelle lui-même) ne décrit pas à proprement parler les MT que nous connaissons. Je crois que la présentation que nous connaissons est due à Kleene. Le mémoire de thèse de Turing parle de machines à oracle. En revanche Alan M. Turing: Computability and lambda-Definability. J. Symb. Log. 2(4): 153-163 (1937) est important, car il relie la calculabilité par MT à celle original définie par Church. Pierre de Lyon (d) 5 octobre 2008 à 19:09 (CEST)

Il me semble que le lien est déjà introduit (mais peut-être pas complètement démontré, je te laisse en juger ça dépasse mes compétences) dans l'annexe du 28 août 1936 de On computable numbers, intitulée Computability and effective calculability (mais « calculabilité et lambda-définissabilité » dans la traduction française). - Eusebius ^[causons] 5 octobre 2008 à 19:26 (CEST)

Il y a deux articles, "On computable numbers" (CT) et celui que je cite. Si mes souvenirs sont bons, l'équivalence est seulement évoquée rapidement par AT dans CT et il a jugé opportun d'y revenir dans un deuxième article. Pierre de Lyon (d) 6 octobre 2008 à 18:44 (CEST)

--

Je connaissais pas ce néologisme « ordinatique ». Qu'est-ce au juste? Pierre de Lyon (d) 5 octobre 2008 à 19:13 (CEST)

Machines artisanales

Des avis autres que le mien sur cet ajout répété à l'article? [1]

Zandr4^[Kupopo ?] 26 juillet 2012 à 17:01 (CEST)

Pourrais-tu préciser le thème du débat que tu souhaites lancer? --Pierre de Lyon (d) 2 août 2012 à 12:43 (CEST)

Oui. Suis-je à côté de la plaque lorsque je considère que la construction d'une machine de Turing en lego n'est pas un évènement suffisamment important pour être mentionné dans une encyclopédie, compte tenu des sources apportées ? Zandr4^[Kupopo ?] 4 août 2012 à 09:13 (CEST)

C’est anecdotique, pas de doute à ce sujet, d’un autre côté c’est effectué à l’occasion de l’année Turing, et c’est passé à la une de journaux (au moins en ligne) grand public à l’échelle nationale (lemonde.fr) si je me souviens bien, ce qui n’est pas si anecdotique que ça pour quelque chose qui concerne essentiellement l’informatique thérorique. C’est une manière détournée de signaler l’importance du sujet. Et puis tous ces exemples sont plutôt sympathiques et ne font de mal à personne :). Peut être que le paragraphe mérite d’être retravaillé et rédigé un peu mieux cependant, je vais m’y atteler TomT0m (d) 4 août 2012 à 10:51 (CEST)

Tomtom, la machine turing est une bandellette de papier. Montée avec des composant électronique ce modèle à servie à déchiffrer les messages allemands à Londre en 39-45…(j’ai vulgarisé beaucoup), mes respects, (Guyot b.)==>pour les (pourparlers) 20 mars 2013 à 16:11 (CET)

Pas exactement non, ce qui a servi a déchiffrer les message allemand n’était pas une machine de Turing à proprement parler. — TomT0m ^[bla] 20 mars 2013 à 17:03 (CET)

c’est pour çà que j’ai dit vulgariser. en lisant l’article croit que c’est un ordi. Ce n’est pas. C’est une expérience de pensée..(je vulgarise..), cordialement tomtom, mes respects, (Guyot b.)==>pour les (pourparlers) 20 mars 2013 à 18:53 (CET)

qu’est-ce que la machine de turing

?, mes respects, (Guyot b.)==>pour les (pourparlers) 20 mars 2013 à 16:25 (CET)

Je me le demande aussi ce n'est pas clair !!!! — Le message qui précède, non signé, a été déposé par Ouestu (discuter), le 26 avril 2015 à 16:49‎

L'article commence par une définition (que je trouve précise ) de ce qu'est une machine de Turing. Pourriez-vous préciser ce que vous ne comprenez pas dans cette définition pour que nous puissions l'améliorer (si c'est possible ). --Pierre de Lyon (discuter) 3 mai 2015 à 11:47 (CEST)

Modèle abstrait du fonctionnement des appareils mécaniques de calcul ou modèle du calculateur humain ?

L'article commencer par

Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ».

Je pense que cela trahit la pensée d'Alan Turing qui voyait ses machines comme un modèle de calculateur humain. Je suis favorable à garder la première phrase et je me demande comment modifier la deuxième qui attribue les machine de Turing à Alan Turing en ne trahissant pas sa pensée. --Pierre de Lyon (discuter) 10 mai 2016 à 14:18 (CEST)

Les petits inventeurs associés

(Cette discussion rejoint la discussion « Machines artisanales » ci-dessus, de 2012-2013). Les exemples de la section « Réalisation d'une machine de Turing » me posent un problème sérieux, de notoriété (donc de valeur encyclopédique) et de sources :

• l'exemple d'avril 2011 n'est étayé que par un blog abandonné depuis 2012 ;
• celui de mars 2012 est à la rigueur acceptable (un site dépendant de l'ENS de Lyon et un article du Monde) ;
• celui de décembre 2013 est étayé par un site dédié (non commercial) et bien fichu, un article sur le site http://images.math.cnrs.fr/ et de nombreux articles de presse (pas seulement celui de Ouest-France référencé dans notre article) ;
• celui d'octobre 2020 et février 2021, rédigé par le concepteur de la machine (cf. le commentaire de l'une de ses diffs), n'était étayé que par son site (commercial !) jusqu'à ce que je supprimasse la réf.

Malgré l'intérêt de tous ces exemples et en raison de la faiblesse des sources en l'état, je suggère de supprimer le premier et le dernier de ces quatre exemples. — Ariel (discuter) 10 février 2021 à 07:39 (CET)

Je propose d'attendre encore quelques jours pour que l'auteur de la dernière réalisation puisse apporter une référence. -- ManiacParisien (discuter) 10 février 2021 à 07:51 (CET)