[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/decider-turing-machine-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/decider-turing-machine-wikipedia\/","headline":"D\u00e9cider (Turing Machine) – Wikipedia wiki","name":"D\u00e9cider (Turing Machine) – Wikipedia wiki","description":"before-content-x4 Machine Turing qui s’arr\u00eate pour toute entr\u00e9e after-content-x4 En th\u00e9orie de la calculabilit\u00e9, un d\u00e9cideur est une machine Turing","datePublished":"2022-01-03","dateModified":"2022-01-03","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c6f7ed29a2b4a62d3b6af05cd91a58ffc6094201","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c6f7ed29a2b4a62d3b6af05cd91a58ffc6094201","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/decider-turing-machine-wikipedia\/","wordCount":2811,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Machine Turing qui s’arr\u00eate pour toute entr\u00e9e        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4En th\u00e9orie de la calculabilit\u00e9, un d\u00e9cideur est une machine Turing qui s’arr\u00eate pour chaque entr\u00e9e. [d’abord] Un d\u00e9cideur est \u00e9galement appel\u00e9 Machine de Turing totale [2] car il repr\u00e9sente une fonction totale. Parce que cela s’arr\u00eate toujours, une telle machine est en mesure de d\u00e9cider si une cha\u00eene donn\u00e9e est membre d’un langage formel. La classe de langues qui peut \u00eatre d\u00e9cid\u00e9e par ces machines est l’ensemble des langues r\u00e9cursives. Compte tenu d’une machine de Turing arbitraire, d\u00e9terminer s’il s’agit d’un d\u00e9cideur est un probl\u00e8me ind\u00e9cidable. Il s’agit d’une variante du probl\u00e8me d’arr\u00eat, qui demande si une machine de Turing s’arr\u00eate sur une entr\u00e9e sp\u00e9cifique.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4 Table of ContentsFonctions calculables par des machines totales de Turing [ modifier ]] Relation avec les machines Turing partielles [ modifier ]] L’ensemble des indices des machines de Turing total [ modifier ]] Provabilit\u00e9 [ modifier ]] Voir \u00e9galement [ modifier ]] Les r\u00e9f\u00e9rences [ modifier ]] Fonctions calculables par des machines totales de Turing [ modifier ]] En pratique, de nombreuses fonctions d’int\u00e9r\u00eat sont calculables par des machines qui s’arr\u00eatent toujours. Une machine qui utilise uniquement une m\u00e9moire finie sur une entr\u00e9e particuli\u00e8re peut \u00eatre forc\u00e9e de s’arr\u00eater pour chaque entr\u00e9e en restreignant ses capacit\u00e9s de contr\u00f4le de flux afin qu’aucune entr\u00e9e ne fasse jamais entrer la machine \u00e0 entrer une boucle infinie. \u00c0 titre d’exemple trivial, une machine mettant en \u0153uvre un arbre de d\u00e9cision fine s’arr\u00eatera toujours. Il n’est pas n\u00e9cessaire que la machine soit enti\u00e8rement exempte de capacit\u00e9s de boucle, cependant, de garantir l’arr\u00eat. Si nous restreignions les boucles de taille de mani\u00e8re pr\u00e9visible (comme la boucle FOR dans la base), nous pouvons exprimer toutes les fonctions r\u00e9cursives primitives (Meyer et Ritchie, 1967). Un exemple d’une telle machine est fourni par le langage de programmation de jouets pl- {goto} de Brainerd et Landweber (1974).        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Nous pouvons encore d\u00e9finir un langage de programmation dans lequel nous pouvons nous assurer que les fonctions encore plus sophistiqu\u00e9es s’arr\u00eatent toujours. Par exemple, la fonction Ackermann, qui n’est pas r\u00e9cursive primitive, est n\u00e9anmoins une fonction informatique totale calculable par un syst\u00e8me de r\u00e9\u00e9criture de terme avec une commande de r\u00e9duction sur ses arguments (Ohlebusch, 2002, pp. 67). Malgr\u00e9 les exemples ci-dessus de langages de programmation qui garantissent la fin des programmes, il n’existe pas de langage de programmation qui capture exactement les fonctions r\u00e9cursives totales, c’est-\u00e0-dire les fonctions qui peuvent \u00eatre calcul\u00e9es par une machine Turing qui s’arr\u00eate toujours. En effet, l’existence d’un tel langage de programmation serait une contradiction avec la non-d\u00e9cidabilit\u00e9 du probl\u00e8me du probl\u00e8me si une machine Turing s’arr\u00eate sur chaque entr\u00e9e. Relation avec les machines Turing partielles [ modifier ]] Une machine Turing g\u00e9n\u00e9rale calculera une fonction partielle. Deux questions peuvent \u00eatre pos\u00e9es sur la relation entre les machines de Turing partiels et les machines Total Turing: Chaque fonction partielle calculable par une machine de Turing partiel peut-elle \u00eatre \u00e9tendue (c’est-\u00e0-dire, son domaine a-t-il agrandi) pour devenir une fonction totale calculable? Est-il possible de modifier la d\u00e9finition d’une machine Turing afin qu’une classe particuli\u00e8re de machines Turing totales, en calculant toutes les fonctions calculables totales, puisse \u00eatre trouv\u00e9e? La r\u00e9ponse \u00e0 chacune de ces questions est non. Le th\u00e9or\u00e8me suivant montre que les fonctions calculables par des machines qui s’arr\u00eatent toujours n’incluent pas d’extensions de toutes les fonctions calculables partielles, ce qui implique que la premi\u00e8re question ci-dessus a une r\u00e9ponse n\u00e9gative. Ce fait est \u00e9troitement li\u00e9 \u00e0 l’abandon algorithmique du probl\u00e8me d’arr\u00eat. Th\u00e9or\u00e8me – Il existe des fonctions partielles calculables Turing qui n’ont aucune extension \u00e0 une fonction calculable totale Turing. En particulier, la fonction partielle F d\u00e9fini pour que F ( n ) = m Si et seulement si la machine Turing avec index n s’arr\u00eate sur l’entr\u00e9e 0 avec sortie m n’a pas d’extension \u00e0 une fonction calculable totale. En effet, si g une fonction calculable totale s’\u00e9tendait F alors g serait calculable par une machine Turing; r\u00e9parer C’est comme l’indice d’une telle machine. Construisez une machine Turing M , en utilisant le th\u00e9or\u00e8me de la r\u00e9cursivit\u00e9 de Kleene, qui en entr\u00e9e 0 simule la machine avec l’index C’est ex\u00e9cuter sur un index n M pour M (Ainsi la machine M peut produire un indice de lui-m\u00eame; C’est le r\u00f4le du th\u00e9or\u00e8me de la r\u00e9cursivit\u00e9). Par hypoth\u00e8se, cette simulation reviendra \u00e9ventuellement une r\u00e9ponse. D\u00e9finir M [ clarifier ]] pour que si g ( n M ) = m puis la valeur de retour de M est m + d’abord {displaystyle m + 1} . Ainsi F ( n M ), la vraie valeur de retour de M en entr\u00e9e 0 , n’\u00e9galera pas g ( n M ). Ainsi g ne s’\u00e9tend pas F . La deuxi\u00e8me question demande, en substance, s’il existe un autre mod\u00e8le de calcul raisonnable qui ne calcule que les fonctions totales et calcule toutes les fonctions calculables totales. De mani\u00e8re informelle, si un tel mod\u00e8le existait, chacun de ses ordinateurs pourrait \u00eatre simul\u00e9 par une machine Turing. Ainsi, si ce nouveau mod\u00e8le de calcul consistait en une s\u00e9quence M d’abord , M 2 , … {displayStyle m_ {1}, m_ {2}, ldots} des machines, il y aurait une s\u00e9quence r\u00e9cursivement \u00e9num\u00e9rable T d’abord , … T 2 , … {displayStyle t_ {1}, ldots t_ {2}, ldots} de machines Turing qui calculent les fonctions totales et que chaque fonction totale calculable soit calculable par l’une des machines T je . C’est impossible, car une machine T pourrait \u00eatre construit de telle sorte que sur l’entr\u00e9e je la machine T Retour T je ( je ) + d’abord {displayStyle t_ {i} (i) +1,} . Cette machine ne peut \u00eatre \u00e9quivalente \u00e0 aucune machine T sur la liste: supposons que ce soit sur la liste de l’index J . Alors T J ( J ) = T J ( J ) + d’abord {displaystyle T_{j}(j)=T_{j}(j)+1,} , qui ne renvoie pas de r\u00e9sultat entier. Par cons\u00e9quent, il ne peut pas \u00eatre total, mais la fonction par construction doit \u00eatre totale (si les fonctions totales sont \u00e9num\u00e9rables r\u00e9cursivement, alors cette fonction peut \u00eatre construite), ce qui est une contradiction. Cela montre que la deuxi\u00e8me question a une r\u00e9ponse n\u00e9gative. L’ensemble des indices des machines de Turing total [ modifier ]] Le probl\u00e8me de d\u00e9cision de savoir si la machine Turing avec index C’est L’arr\u00eat sur chaque entr\u00e9e n’est pas d\u00e9cidable. En fait, ce probl\u00e8me est au niveau Pi 2 0 {displayStyle pi _ {2} ^ {0}} de la hi\u00e9rarchie arithm\u00e9tique. Ainsi, ce probl\u00e8me est strictement plus difficile que le probl\u00e8me d’arr\u00eat, qui demande si la machine avec index C’est s’arr\u00eate sur l’entr\u00e9e 0 . Intuitivement, cette diff\u00e9rence de non-solvabilit\u00e9 est due au fait que chaque instance du probl\u00e8me de la “machine totale” repr\u00e9sente l’infini de nombreuses instances du probl\u00e8me d’arr\u00eat. Provabilit\u00e9 [ modifier ]] On peut \u00eatre int\u00e9ress\u00e9 non seulement par la question de savoir si une machine Turing est totale, mais aussi pour savoir si cela peut \u00eatre prouv\u00e9 dans un certain syst\u00e8me logique, comme l’arithm\u00e9tique de Premier Ordre. Dans un syst\u00e8me d’\u00e9preuve sonore, chaque machine de Turing prouvable totale est en effet totale, mais l’inverse n’est pas vrai: de mani\u00e8re informelle, pour chaque syst\u00e8me d’\u00e9preuve de premier ordre qui est suffisamment fort (y compris l’arithm\u00e9tique d’arano), il existe des machines Turing qui sont suppos\u00e9es \u00eatre total, mais ne peut \u00eatre prouv\u00e9 en tant que tel, sauf si le syst\u00e8me est incoh\u00e9rent (auquel cas on peut prouver n’importe quoi). La preuve de leur totalit\u00e9 repose sur certaines hypoth\u00e8ses ou n\u00e9cessite un autre syst\u00e8me de preuve. Ainsi, comme on peut \u00e9num\u00e9rer toutes les preuves du syst\u00e8me de preuve, on peut construire une machine Turing sur l’entr\u00e9e n qui passe par les n preuves n et rechercher une contradiction. S’il en trouve un, il entre dans une boucle infinie et ne s’arr\u00eate jamais; Sinon, cela s’arr\u00eate. Si le syst\u00e8me est coh\u00e9rent, la machine Turing s’arr\u00eate sur chaque entr\u00e9e, mais on ne peut pas le prouver dans un syst\u00e8me de preuve suffisamment fort en raison des th\u00e9or\u00e8mes d’incompl\u00e9tude de G\u00f6del. On peut \u00e9galement cr\u00e9er une machine Turing qui s’arr\u00eate si et seulement si le syst\u00e8me de preuve est incoh\u00e9rent, et est donc non total pour un syst\u00e8me coh\u00e9rent mais ne peut pas \u00eatre prouv\u00e9 tel: il s’agit d’une machine Turing qui, quelle que soit l’entr\u00e9e, \u00e9num\u00e8re toutes les preuves et s’arr\u00eate sur une contradiction. Une machine Turing qui passe par des s\u00e9quences de Goodstein et s’arr\u00eate \u00e0 z\u00e9ro est totale mais ne peut pas \u00eatre prouv\u00e9e comme telle dans l’arithm\u00e9tique d’arano. Voir \u00e9galement [ modifier ]] Les r\u00e9f\u00e9rences [ modifier ]] Brainerd, W.S., Landweber, L.H. (1974), Th\u00e9orie du calcul , Wiley. Meyer, A.R., Ritchie, D.M. (1967), La complexit\u00e9 des programmes de boucle , Proc. des r\u00e9unions nationales de l’ACM, 465. Sipser, M. (2006), Introduction \u00e0 la th\u00e9orie du calcul , PWS Publishing Co. Choisi, D.C. (1997), Automates et calculabilit\u00e9 , Springer. Ohlebusch, E. (2002), Sujets avanc\u00e9s dans la r\u00e9\u00e9criture du terme , Springer.          (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en2fr\/wiki28\/decider-turing-machine-wikipedia\/#breadcrumbitem","name":"D\u00e9cider (Turing Machine) – Wikipedia wiki"}}]}]