AGENCE FÉDÉRALE POUR L'ÉDUCATION INSTITUTION D'ENSEIGNEMENT D'ÉTAT D'ENSEIGNEMENT PROFESSIONNEL SUPÉRIEUR « UNIVERSITÉ D'ÉTAT DE VORONEZH » T.K. Katsaran, L.N. Stroeva MACHINE DE TURING ET FONCTIONS RÉCURSIVES Manuel pour les universités Centre d'édition et d'impression de l'Université d'État de Voronej 2008 Approuvé par le conseil scientifique et méthodologique de la faculté de PMM le 25 mai 2008, protocole n° 9 Réviseur Docteur en sciences techniques, Prof. Département de méthodes mathématiques pour la recherche opérationnelle T.M. Ledeneva Le manuel a été préparé au Département des oscillations non linéaires, Faculté de mathématiques mécaniques, Université d'État de Voronej. Recommandé pour les étudiants de 1ère année de la Faculté de mathématiques appliquées et de mathématiques des branches VSU, Starooskolsky et Liskinsky de VSU. Pour la spécialité 010500 – Mathématiques appliquées et informatique INTRODUCTION Le mot « algorithme » vient de algorithmi – l'orthographe latine du nom du mathématicien et astronome ouzbek qui vécut aux VIIIe-IXe siècles (783-850), Muhammad ben Musa al- Khwarizmi. Le plus grand mathématicien du Khorezm (une ville de l’Ouzbékistan moderne) était connu sous ce nom dans l’Europe médiévale. Dans son livre « On Indian Counting », il a formulé les règles d'écriture des nombres naturels en utilisant des chiffres arabes et les règles pour les utiliser. Ensuite, le concept d’algorithme a commencé à être utilisé dans un sens plus large et pas seulement en mathématiques. Pour les mathématiciens comme pour les praticiens, le concept d’algorithme est important. Ainsi, nous pouvons dire qu'un algorithme est une prescription précise pour exécuter un certain système d'opérations dans un certain ordre pour résoudre tous les problèmes du même type, définissant une séquence d'actions qui garantit l'obtention du résultat requis à partir des données initiales. A noter qu'il ne s'agit pas ici d'une définition du concept « algorithme », mais seulement de sa description, de son sens intuitif. L'algorithme peut être conçu pour être exécuté soit par une personne, soit par un appareil automatique. Cette idée d’algorithme n’est pas rigoureuse d’un point de vue mathématique, puisqu’elle utilise des notions telles que « instructions exactes » et « données initiales », qui, d’une manière générale, ne sont pas strictement définies. Une caractéristique de tout algorithme est sa capacité à résoudre une certaine classe de problèmes. Par exemple, il peut s'agir d'un algorithme permettant de résoudre des systèmes d'équations linéaires, de trouver le chemin le plus court dans un graphique, etc. Créer un algorithme, même le plus simple, est un processus créatif. Il est accessible exclusivement aux êtres vivants, et pendant longtemps on a cru qu'il était réservé aux humains. Une autre chose est la mise en œuvre d'un algorithme existant. Il peut être confié à un sujet ou à un objet qui n'est pas obligé d'approfondir l'essence du sujet, et peut-être n'est-il pas capable de le comprendre. Un tel sujet ou objet est généralement appelé un interprète formel. Un exemple d'interprète formel est une machine à laver automatique, qui exécute strictement les actions qui lui sont prescrites, même si vous avez oublié d'y mettre de la poudre. Une personne peut également agir en tant qu'artiste formel, mais tout d'abord, divers appareils automatiques, y compris un ordinateur, sont des artistes formels. Chaque algorithme est créé en pensant à un interprète très spécifique. Les actions que l'interprète peut effectuer sont appelées ses actions autorisées. L'ensemble des actions autorisées forme un système de commandes d'interprète. L'algorithme doit contenir uniquement les actions autorisées pour un interprète donné. Par conséquent, plusieurs propriétés générales des algorithmes sont généralement formulées pour distinguer les algorithmes des autres instructions. L'algorithme doit avoir les propriétés suivantes. Discrétion (discontinuité, séparation) – l'algorithme doit représenter le processus de résolution d'un problème comme une exécution séquentielle d'étapes simples (ou préalablement définies). Chaque action fournie par l'algorithme n'est exécutée qu'une fois l'exécution de la précédente terminée. Certitude – chaque règle de l’algorithme doit être claire, sans ambiguïté et ne laisser aucune place à l’arbitraire. Grâce à cette propriété, l'exécution de l'algorithme est de nature mécanique et ne nécessite aucune instruction ou information supplémentaire sur le problème à résoudre. Efficacité (finitude) – l'algorithme doit conduire à résoudre le problème en un nombre fini d'étapes. 4 Massivité - l'algorithme de résolution du problème est développé sous une forme générale, c'est-à-dire qu'il devrait être applicable à une certaine classe de problèmes qui ne diffèrent que par les données initiales. Dans ce cas, les données initiales peuvent être sélectionnées dans une certaine zone, appelée zone d'applicabilité de l'algorithme. La théorie des algorithmes est une branche des mathématiques qui étudie les propriétés générales des algorithmes. Il existe des théories qualitatives et métriques des algorithmes. Le principal problème de la théorie qualitative des algorithmes est le problème de la construction d’un algorithme ayant des propriétés spécifiées. Ce problème est appelé problème algorithmique. La théorie métrique des algorithmes examine les algorithmes en termes de complexité. Cette branche de la théorie des algorithmes est également connue sous le nom de théorie de la complexité algorithmique. Lors de la recherche de solutions à certains problèmes, il a fallu beaucoup de temps pour trouver l'algorithme approprié. Des exemples de tels problèmes sont : a) indiquer une méthode selon laquelle, pour toute formule de prédicat, dans un nombre fini d'opérations, on peut découvrir si elle est identiquement vraie ou non ; b) l'équation diophantienne (une équation algébrique à coefficients entiers) est-elle résoluble en nombres entiers ? Comme il n'a pas été possible de trouver des algorithmes pour résoudre ces problèmes, l'hypothèse est apparue que de tels algorithmes n'existent pas du tout, ce qui a été prouvé : le premier problème a été résolu par A. Church et le second par Yu.V. Matiyasevich et G.V. Chudnovski. Il est en principe impossible de le prouver en utilisant le concept intuitif d’un algorithme. Par conséquent, des tentatives ont été faites pour donner une définition mathématique précise du concept d’algorithme. Au milieu des années 30 du XXe siècle, S.K. Kleene, A.A. Markov, E. Post, A. Turing, A. Church et d'autres ont proposé diverses définitions mathématiques 5 du concept d'algorithme. Par la suite, il a été prouvé que ces différentes définitions mathématiques formelles sont en quelque sorte équivalentes : elles calculent le même ensemble de fonctions. Cela suggère que les principales caractéristiques du concept intuitif d’algorithme semblent être correctement capturées dans ces définitions. Nous considérons ensuite un raffinement mathématique de l'algorithme proposé par A. Turing, appelé machine de Turing. 6 1. MACHINE DE TURING § 1. Modèle mathématique de la machine de Turing L'idée de créer une machine de Turing, proposée par le mathématicien anglais A. Turing dans les années trente du 20e siècle, est associée à sa tentative de donner un définition mathématique précise du concept d'algorithme. Une machine de Turing (MT) est un modèle mathématique d'un ordinateur numérique idéalisé. Une machine de Turing est le même objet mathématique qu'une fonction, une dérivée, une intégrale, un groupe, etc. Tout comme d'autres concepts mathématiques, le concept de machine de Turing reflète la réalité objective et modélise certains processus réels. Pour décrire l'algorithme MT, il convient d'imaginer un dispositif composé de quatre parties : bande, tête de lecture, dispositif de contrôle et mémoire interne. 1. La bande est supposée potentiellement infinie, divisée en cellules (cellules égales). Si nécessaire, une cellule vide est attachée à la première ou à la dernière cellule dans laquelle se trouvent les symboles. La machine fonctionne dans le temps, considéré comme discret, et ses instants sont numérotés 1, 2, 3, …. A tout moment, la bande contient un nombre fini de cellules. Un seul symbole (lettre) de l'alphabet externe A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 peut être écrit dans des cellules à un instant discret. Une cellule vide est désignée par le symbole L, et le symbole L lui-même est appelé vide, tandis que les symboles restants sont appelés non vides. Dans cet alphabet A, les informations fournies au MT sont codées sous la forme d'un mot (un ensemble fini et ordonné de symboles). La machine « traite » les informations présentées sous la forme d’un mot en un nouveau mot. 2. La tête de lecture (un certain élément de lecture) se déplace le long de la bande de sorte qu'à chaque instant, elle visualise exactement une cellule de la bande. La tête peut lire le contenu d'une cellule et y écrire un nouveau caractère de l'alphabet A. En un cycle d'opération, elle ne peut déplacer qu'une seule cellule vers la droite (R), la gauche (L) ou rester en place (N ). Notons l'ensemble des mouvements (décalages) de la tête D = (P, L, N). Si à un instant donné t la tête est dans la cellule la plus à l'extérieur et se déplace vers la cellule manquante, alors une nouvelle cellule vide est ajoutée, au dessus de laquelle la tête se trouvera à l'instant t + 1. 3. La mémoire interne de la machine est un certain ensemble fini d'états internes Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . Nous supposerons que la puissance |Q | ³ 2. Deux états de la machine ont une signification particulière : q1 est l'état interne initial (il peut y avoir plusieurs états internes initiaux), q0 est l'état final ou état d'arrêt (il y a toujours un état final). A chaque instant, le MT est caractérisé par la position de la tête et l'état interne. Par exemple, sous la cellule au dessus de laquelle se trouve la tête, est indiqué l'état interne de la machine. ¯ a2 a1 L a2 a3 q1 4. A chaque instant t, le dispositif de contrôle, en fonction du symbole présent sur la bande en cours de lecture et de l'état interne de la machine, effectue les actions suivantes : 1) change le symbole ai lu à l'instant t à un nouveau symbole a j (en particulier, le laisse inchangé, c'est-à-dire ai = a j) ; 2) déplace la tête dans l'une des directions suivantes : N, L, R ; 3) change l'état interne de la machine 8 qi existant à l'instant t en un nouveau q j dans lequel la machine se trouvera à l'instant t +1 (il se peut que qi = q j). De telles actions du dispositif de commande sont appelées une commande, qui peut être écrite sous la forme : qi ai ® a j D q j , (1) où qi est l'état interne de la machine à ce moment-là ; a i – le symbole lu à ce moment ; a j – le symbole en lequel le symbole a i change (peut être ai = a j) ; le symbole D est soit N, soit L, soit P et indique le sens de déplacement de la tête ; q j est l'état interne de la machine à l'instant suivant (peut-être qi = q j). Les expressions qi ai et a j D q j sont appelées respectivement les côtés gauche et droit de cette commande. Le nombre de commandes dans lesquelles les membres de gauche sont deux à deux distincts est un nombre fini, puisque les ensembles Q \ (q 0 ) et A sont finis. Il n'existe pas de commandes avec des côtés gauches identiques, c'est-à-dire que si le programme machine T contient les expressions qi ai ® a j D q j et qt at ® ak D qk , alors qi ¹ qt ou ai ¹ at et D O (P, L, N ). L’ensemble de toutes les instructions est appelé programme machine de Turing. Le nombre maximum de commandes dans un programme est (n + 1) x m, où n + 1 = A et m + 1 = Q. On pense que l'état final de la commande q0 ne peut apparaître que sur le côté droit de la commande, l'état initial q1 peut apparaître à la fois sur le côté gauche et droit de la commande. L'exécution d'une commande s'appelle une étape. Le calcul (ou le fonctionnement) d'une machine de Turing est une séquence d'étapes les unes après les autres sans saut, en commençant par la première. Ainsi, MT est donné si quatre ensembles finis sont connus : l'alphabet externe A, l'alphabet interne Q, l'ensemble D des mouvements de tête et le programme machine, qui est un ensemble fini de commandes. 9 § 2. Fonctionnement d'une machine de Turing Le fonctionnement de la machine est entièrement déterminé par la tâche au premier moment (initial) : 1) des mots sur la bande, c'est-à-dire une séquence de symboles écrits dans les cellules de la bande (un le mot est obtenu en lisant ces symboles à travers les cellules de la bande de gauche à droite) ; 2) position de la tête ; 3) l'état interne de la machine. La combinaison de ces trois conditions (pour le moment) est appelée configuration (pour le moment). Généralement, au moment initial, l'état interne de la machine est q1 et la tête se trouve soit au-dessus de la première cellule gauche, soit de la première cellule droite de la bande. Un mot donné sur la bande avec l'état initial q1 et la position de la tête au-dessus du premier mot est appelé configuration initiale. Sinon, on dit que la machine de Turing n'est pas applicable à un mot de configuration initiale. Autrement dit, à l'instant initial la configuration est représentable sous la forme suivante : sur une bande constituée d'un certain nombre de cellules, dans chaque cellule est écrit un des symboles de l'alphabet externe A, la tête est située au dessus du premier la cellule gauche ou première droite de la bande et celle interne. la position de la machine est q1. Le mot résultant sur la bande et la position de la tête résultant de la mise en œuvre de cette commande est appelé configuration finale. Par exemple, si au moment initial le mot a1La 2 a1a1 est écrit sur la bande, alors la configuration initiale ressemblera à : a1 a2 L a1 a1 q1 (sous la cellule au dessus de laquelle se trouve la tête, l'état interne de la machine est indiqué). dix

Thème « Machine de Turing » dans un cours d'informatique à l'école

DANS. Falina,
Moscou

Dans de nombreux manuels d'informatique, lors de l'étude du concept et des propriétés d'un algorithme, il existe des phrases avec le contenu suivant : « … il existe de nombreuses façons différentes d'écrire le même algorithme, par exemple en écrivant sous forme de texte, en écrivant sous la forme d'un organigramme, écriture dans un langage algorithmique, représentation d'un algorithme sous la forme d'une machine de Turing ou d'une machine de poste... » Malheureusement, ces types de phrases sont les seules qui mentionnent une machine de Turing. Sans aucun doute, le volume d'heures consacrées à l'étude des algorithmes ne permet pas d'inclure également dans ce thème l'étude des manières d'écrire un algorithme sous la forme d'une machine de Turing. Mais ce sujet est extrêmement intéressant, important et utile pour les écoliers, notamment ceux qui s'intéressent à l'informatique.

Le sujet « Machine de Turing » peut être étudié de la 8e à la 11e année dans le cadre du thème « Processus d'information ». Traitement de l'information », dans les cours au choix, dans le système d'enseignement complémentaire, par exemple dans les écoles pour jeunes programmeurs. L'étude de ce sujet peut être accompagnée d'un support informatique si l'enseignant dispose d'un logiciel de simulation « Turing Machine ». Dans les cours de programmation avancés, les étudiants peuvent écrire indépendamment un programme de machine de Turing. Dans le cadre de cet article, nous vous proposons un atelier de résolution de problèmes sur le thème « Machine de Turing ». Du matériel théorique sur ce sujet a été publié plus d'une fois dans les pages du journal Informatics, par exemple, dans le n° 3/2004, un article d'I.N. Falina « Éléments de théorie des algorithmes ».

Une machine de Turing est une construction mathématique stricte, un appareil mathématique (similaire, par exemple, à l'appareil d'équations différentielles), créé pour résoudre certains problèmes. Cet appareil mathématique a été appelé « machine » car, en termes de description de ses éléments constitutifs et de son fonctionnement, il s'apparente à un ordinateur. La différence fondamentale entre une machine de Turing et des ordinateurs est que son périphérique de stockage est une bande infinie : dans les vrais ordinateurs, le périphérique de stockage peut être aussi grand que vous le souhaitez, mais il doit être fini. Une machine de Turing ne peut être réalisée précisément parce que sa bande est infinie. En ce sens, il est plus puissant que n’importe quelle machine informatique.

Chaque machine de Turing comporte deux parties :

1)illimité aller-retour ruban, divisé en cellules ;

2) machine(tête de lecture/écriture contrôlée par logiciel).

Chaque machine de Turing est associée à deux derniers alphabets: alphabet des symboles d'entrée A = (a 0 , a 1 , ..., a m ) et alphabet des états Q = (q 0 , q 1 , ..., q p ). (Différentes machines Turing peuvent être associées à différents alphabets. UN Et Q.) L'état q 0 est appelé passif. On pense que si la machine entre dans cet état, elle a terminé son travail. L'état q 1 est appelé initial. Dans cet état, la machine commence son travail.

Le mot saisi est placé sur la bande une lettre à la fois dans des cellules consécutives. À gauche et à droite du mot saisi, il n'y a que des cellules vides (dans l'alphabet UN comprend toujours une lettre vide UN 0 est le signe que la cellule est vide).

La machine peut se déplacer le long de la bande vers la gauche ou la droite, lire le contenu des cellules et écrire des lettres dans les cellules. Vous trouverez ci-dessous un dessin schématique d'une machine de Turing, dont l'automate examine la première cellule contenant des données.

La machine ne « voit » qu’une seule cellule à chaque fois. Selon quelle lettre ai il voit, et aussi en fonction de son état qj La machine peut effectuer les actions suivantes :

• · écrire une nouvelle lettre dans la cellule observée ;
• · décaler la bande d'une cellule vers la droite/gauche ou rester immobile ;
• · passer à un nouvel état.

Autrement dit, une machine de Turing comporte trois types d’opérations. A chaque fois pour le couple suivant ( qj, un je) une machine de Turing exécute une commande composée de trois opérations avec certains paramètres.

Le programme de la machine Turing est un tableau avec une commande écrite dans chaque cellule.

Cellule ( qj, un je) est déterminé par deux paramètres : le symbole alphabétique et l'état de la machine. La commande est une indication : où déplacer la tête de lecture/écriture, quel caractère écrire dans la cellule actuelle, dans quel état la machine doit aller. Pour indiquer le sens de déplacement de la machine, nous utilisons l'une des trois lettres suivantes : « L » (gauche), « P » (droite) ou « N » (stationnaire).

Une fois que la machine a exécuté la commande suivante, elle passe à l'état qm(qui peut dans un cas particulier coïncider avec l'état précédent qj). La commande suivante devrait être trouvée dans mème ligne du tableau à l'intersection avec la colonne Al(lettre Al la machine voit après le quart de travail).

Admettons que lorsque la bande contient un mot d'entrée, alors la machine est située contre une cellule dans l'état q 1. Pendant le fonctionnement, l'automate sautera d'une cellule du programme (table) à une autre jusqu'à atteindre la cellule dans laquelle il est écrit que l'automate doit passer dans l'état q 0 . Ces cellules sont appelées arrêter les cellules. Ayant atteint une telle cellule, la machine de Turing s'arrête.

Malgré sa conception simple, une machine de Turing peut effectuer toutes les transformations possibles de mots, mettant ainsi en œuvre tous les algorithmes possibles.

Exemple. Vous devez construire une machine de Turing qui ajoute un à un nombre sur une bande. Le mot d'entrée est constitué de chiffres entiers décimaux écrits dans des cellules consécutives de la bande. Au début, la machine est située en face du chiffre le plus à droite du numéro.

Solution. La machine doit ajouter un au dernier chiffre du numéro. Si le dernier chiffre est 9, remplacez-le par 0 et ajoutez un au chiffre précédent. Un programme pour une machine de Turing donnée pourrait ressembler à ceci :

Dans cette machine de Turing q 1 - état de changement de chiffre, q 0 - état d'arrêt. Si vous le pouvez q je la machine voit le chiffre 0..8, puis elle le remplace respectivement par 1..9 et passe à l'état q 0, c'est-à-dire la voiture s'arrête. S'il voit le chiffre 9, alors il le remplace par 0, se déplace vers la gauche, restant dans l'état q je. Cela continue jusqu'à ce que la machine rencontre un nombre inférieur à 9. Si tous les nombres étaient égaux à 9, elle les remplacera par des zéros, écrira 0 à la place du chiffre le plus élevé, se déplacera vers la gauche et écrira 1 dans une cellule vide. Ensuite, il ira à l'état q 0, c'est-à-dire s'arrêtera.

Tâches pratiques

1. La bande de la machine de Turing contient une séquence de symboles « + ». Écrivez un programme pour une machine de Turing qui remplace un symbole «+» sur deux par un «-». Le remplacement commence à l'extrémité droite de la séquence. La machine est capable q 1 regarde l'un des caractères dans la séquence spécifiée. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

2. Étant donné un numéro n dans le système de nombres octaux. Concevoir une machine de Turing qui incrémente un nombre donné nà 1. La machine est capable q 1 regarde un certain chiffre du mot d’entrée. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

3. Étant donné la notation décimale d'un nombre naturel n> 1. Développer une machine de Turing qui réduirait un nombre donné nà 1. La machine est capable q 1 regarde le chiffre droit du nombre. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

4. Étant donné un nombre naturel n> 1. Développer une machine de Turing qui réduirait un nombre donné n par 1, tandis que le chiffre le plus significatif du mot de sortie ne doit pas être 0. Par exemple, si le mot d'entrée était « 100 », alors le mot de sortie doit être « 99 » et non « 099 ». La machine est capable q 1 regarde le chiffre droit du nombre. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

5. Étant donné un tableau de parenthèses ouvrantes et fermantes. Construisez une machine de Turing qui supprimerait les paires de parenthèses mutuelles, c'est-à-dire situé dans une rangée « () ».

Par exemple, étant donné « ) (() (() », vous devez obtenir « ) . . . (( ».

La machine est capable q

6. Étant donné une chaîne de lettres « un" Et " b" Développer une machine de Turing qui déplacera toutes les lettres » un" à gauche, et les lettres " b» - sur le côté droit de la ligne. La machine est capable q 1 regarde le caractère le plus à gauche de la ligne. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

7. Sur la bande de la machine de Turing, il y a un nombre écrit dans le système numérique décimal. Multipliez ce nombre par 2. La machine est capable q 1 regarde le chiffre le plus à gauche du nombre. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

8. Étant donné deux nombres naturels m Et n, présenté dans le système de numérotation unaire. Les jeux de caractères correspondants sont « | » séparés par une cellule vide. La machine est capable q 1 regarde le caractère le plus à droite de la séquence d’entrée. Développer une machine de Turing qui laissera une somme de nombres sur une bande m Et n. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

9. Étant donné deux nombres naturels m Et n, présenté dans le système de numérotation unaire. Les jeux de caractères correspondants sont « | » séparés par une cellule vide. La machine est capable q 1 regarde le caractère le plus à droite de la séquence d’entrée. Développez une machine de Turing qui laissera une différence entre les nombres sur la bande. m Et n. Il est connu que m> n. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

10. Il y a un nombre décimal sur la bande de la machine de Turing. Déterminez si ce nombre est divisible par 5 sans reste. S'il est divisible, écrivez alors le mot « oui » à droite du chiffre, sinon « non ». La machine examine un certain chiffre du numéro saisi. En plus du programme de table lui-même, décrivez en mots ce qui est effectué par la machine dans chaque état.

Capable q 1 machine recherche l'extrémité droite du numéro, capable q 2 - saute le signe «+», lorsqu'il arrive à la fin de la séquence - s'arrête. Capable q 3, la machine remplace le signe « + » par le signe « – » et lorsqu'elle arrive à la fin de la séquence, elle s'arrête.

La solution à ce problème est similaire à l’exemple présenté ci-dessus.

État q 1 - nous diminuons le chiffre le plus bas (suivant) de 1. S'il n'est pas égal à zéro, nous arrêtons immédiatement après la diminution ; si le chiffre le plus bas est 0, alors nous écrivons 9 à la place, décalons vers la gauche et effectuons à nouveau la soustraction . Dans une cage [ un 0 , q 1 ] une machine de Turing ne frappera jamais, elle peut donc rester vide.

Tâche 4 (complication de la tâche 3)

État q 1 - nous diminuons le chiffre mineur (suivant) de 1. S'il est supérieur à 1, alors après la réduction, nous nous arrêtons immédiatement, mais si le chiffre mineur est 0, alors nous écrivons 9 à la place, décalons vers la gauche et effectuons la soustraction encore. Si le chiffre à réduire est 1, alors nous écrivons 0 à la place et passons à l'état q 2 .

État q 2 - après avoir écrit « 0 » dans n'importe quelle position, il est nécessaire d'analyser si ce zéro est le chiffre le plus significatif (c'est-à-dire s'il se trouve à sa gauche dans l'enregistrement de mots de sortie un 0).

État q 3 - si le « 0 » enregistré est le chiffre le plus significatif, alors il doit être supprimé de l'enregistrement de mot de sortie.

Les cellules dans lesquelles la machine de Turing ne pénètre jamais restent vides.

État q 1 : si « ( » est rencontré, alors décalez-vous vers la droite et accédez à l'état q 2 ; si tu as rencontré " un 0", puis arrêtez.

État q 2 : analyse du symbole « ( » pour l'appariement, en cas d'appariement ils doivent voir «) ». Si c'est un hammam, alors retournez à gauche et allez à l'état q 3 .

État q 3 : effacez d’abord « ( », puis « ) » et accédez à q 1 .

Résoudre ce problème pose généralement des difficultés aux écoliers. Lors de l’analyse de la solution à ce problème, vous pouvez procéder, par exemple, de la manière suivante.

Passez en revue les options suivantes pour les mots d'entrée avec vos élèves et demandez-leur de formuler ce qu'une machine de Turing devrait faire, à quoi ressemble le mot de sortie et en quoi ces options diffèrent du point de vue d'une machine de Turing :

aaa ->

a -> le mot de sortie correspond au mot d'entrée, nous parcourons le mot d'entrée jusqu'à ce qu'il se termine.

bbb -> le mot de sortie correspond au mot d'entrée, nous parcourons le mot d'entrée jusqu'à ce qu'il se termine.

b -> le mot de sortie correspond au mot d'entrée, nous parcourons le mot d'entrée jusqu'à ce qu'il se termine.

ab -> le mot de sortie correspond au mot d'entrée, nous parcourons le mot d'entrée jusqu'à ce qu'il se termine.

Résultat de la discussion. Une machine de Turing doit « comprendre » quelle chaîne de lettres elle suit, c'est-à-dire il doit avoir au moins deux états. Laissons l'État q 1 - mouvement le long d'une chaîne de lettres " un", UN q 2 - état de mouvement le long d'une chaîne de lettres " b" Notez que la chaîne peut également être constituée d'une seule lettre. Si nous sommes arrivés au bout de la ligne dans l'état q 1 ou q 2, c'est-à-dire rencontré un 0 , la machine devrait s'arrêter, nous avons traité toute la ligne.

Considérez les options suivantes pour les mots de saisie :

bébé -> abbé

bbbab -> aabbbb

aabbbab -> aaabbbb

Résultat de la discussion. La première version du mot d'entrée peut être traitée séquentiellement comme suit : bébé -> bbb-> revenir à l'extrémité gauche de la chaîne de lettres " b” -> abbé(remplacez la première lettre de cette chaîne par « un"). Pour réaliser ces actions, nous devrons introduire deux nouveaux états et, en plus, clarifier l'état q 2. Ainsi, pour résoudre ce problème, nous devons construire une machine de Turing avec les états suivants :

q 1 - allez vers la droite le long de la chaîne de lettres " un" Si la chaîne se termine un 0, puis allez à q 0 ; s'il se termine par la lettre " b", puis nous allons à q 2 ;

q 2 - allez vers la droite le long de la chaîne de lettres " b" si la chaîne se termine un 0, puis allez à q 0 ; si se termine " un», puis remplacez la lettre « un" sur " b», allez à l'état q 3 (la chaîne des espèces a été remplacée par une chaîne des espèces) ;

q 3 - allez à gauche le long de la chaîne de lettres " b"à son extrémité gauche. Si tu as rencontré un 0 ou " un", puis nous allons à q 4 ;

q 4 - remplacer " b" sur " un" et allez à q 1 (remplacer la chaîne du formulaire par une chaîne du formulaire .

Problème 7

État q 1 - rechercher le chiffre droit (le plus bas) d'un nombre ;

État q 2 - multiplier le chiffre suivant d'un nombre par 2 sans ajouter 1 retenue ;

État q 3 - multiplier le chiffre suivant d'un nombre par 2 avec l'ajout de 1 retenue.

La machine de Turing pour ce programme semble trivialement simple : elle n'a qu'un seul état. Une telle machine de Turing effectue les actions suivantes : efface le trait le plus à droite, recherche un séparateur (cellule vide) et place un trait dans cette cellule vide, formant ainsi une séquence continue de traits de longueur n + m.

Cependant, curieusement, résoudre ce problème pose de grandes difficultés. Très souvent, les étudiants construisent une machine de Turing qui effectue des actions cycliques : pousser séquentiellement vers la droite n coups vers la gauche.

Dans ce cas, leur programme ressemble à ceci :

État q 1 - recherche de séparateur ;

État q 2 - déplacé le trait ;

État q 3 - vérifier la fin (si tous les traits ont été déplacés).

L'exemple de ce problème montre clairement à quelle fréquence les enfants essaient de résoudre un problème d'une manière déjà familière. Il me semble qu'en proposant aux étudiants des problèmes pour construire des machines de Turing, on développe la capacité à trouver des solutions inhabituelles et on développe la capacité de penser de manière créative !

Cette tâche semble assez facile aux écoliers, mais des difficultés surviennent lors de l'arrêt de la machine de Turing. Vous trouverez ci-dessous une version possible d'une machine de Turing pour cette tâche.

Idée de solution (condition d'arrêt). Il y a deux tableaux de traits initiaux sur la bande.

Nous commençons à effacer les traits de l'extrémité gauche du tableau m. Et un par un, nous effaçons le trait le plus à gauche du tableau m et le trait le plus à droite du tableau n. Mais avant d'effacer le trait droit dans le tableau n, on vérifie si c'est le seul (c'est-à-dire le dernier à effacer) ou non.

Décrivons d'abord les états de la machine de Turing qui sont nécessaires pour résoudre notre problème, puis créons un programme de table.

État q 1 - rechercher un séparateur entre les tableaux de traits lors d'un déplacement de droite à gauche ;

État q 2 - recherchez le trait gauche dans le tableau m;

État q 3 - supprimer le trait gauche dans le tableau m;

État q 4 - rechercher un séparateur lors du déplacement de gauche à droite ;

État q 5 - recherchez le bon trait dans le tableau n;

État q 6 - vérifier l'unicité de ce trait dans le tableau n, c'est à dire. déterminer si c'était le dernier ;

État q 7 - si c'était le dernier, alors arrêtez, sinon passez à un nouveau cycle d'exécution de l'algorithme.

Lors de la résolution de ce problème, vous devez faire attention à l'écriture correcte de l'alphabet :

UNE = ( un 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

État q 1 - rechercher l'extrémité droite du numéro ;

État q 2 - analyse du chiffre le moins significatif du nombre ; s'il est égal à « 0 » ou « 5 », c'est-à-dire le nombre est divisible par 5, puis le passage à l'état q 3 , sinon passage à l'état q 5 ;

État q 3 - écrivez la lettre « D » à droite du mot sur la bande ;

État q 4 - écrivez la lettre « A » à droite du mot et arrêtez la machine ;

État q 5 - écrire la lettre « N » à droite du mot ;

État q 6 - écrire la lettre « E » à droite du mot ;

État q 7 - écrivez la lettre « T » à droite du mot et arrêtez la machine.

Propriétés de la machine de Turing en tant qu'algorithme

En utilisant la machine de Turing comme exemple, les propriétés des algorithmes peuvent être clairement vues. Demandez aux élèves de montrer qu’une machine de Turing possède toutes les propriétés d’un algorithme.

Discrétion. Une machine de Turing peut aller à ( k + 1)ème étape seulement après avoir terminé À-ème étape, parce que exactement À- la ème étape détermine ce qui sera ( k + 1)ème étape.

Clarté. A chaque étape, un symbole de l'alphabet est écrit dans la cellule, l'automate effectue un mouvement (L, P, N) et la machine de Turing passe dans l'un des états décrits.

Déterminisme. Chaque cellule du tableau de la machine de Turing ne contient qu'une seule option pour une action. À chaque étape, le résultat est déterminé de manière unique, par conséquent, la séquence d'étapes pour résoudre le problème est déterminée de manière unique, c'est-à-dire Si une machine de Turing reçoit le même mot d’entrée, alors le mot de sortie sera le même à chaque fois.

Productivité. En termes de contenu, les résultats de chaque étape et la séquence entière des étapes sont définis de manière unique ; par conséquent, une machine de Turing correctement écrite passera à l'état en un nombre fini d'étapes. q 0, c'est-à-dire en un nombre fini d’étapes, la réponse à la question problématique sera obtenue.

Caractère de masse. Chaque machine de Turing est définie sur tous les mots admissibles de l'alphabet, c'est la propriété du caractère de masse. Chaque machine de Turing est conçue pour résoudre une classe de problèmes, c'est-à-dire Pour chaque problème, sa propre (nouvelle) machine de Turing est écrite.

DE L'ÉDITEUR

Tous les problèmes évoqués dans l'article peuvent être résolus simplement dans un cahier en dessinant une bande d'information et un programme de table. Mais vous pouvez rendre ce processus plus amusant et visuel : utilisez une implémentation machine - l'interprète de la machine Post et de la machine de Turing « Algo2000 », créée par Radik Zartdinov. Le programme a une interface intuitive et ses exigences sont les plus modérées : un ordinateur IBM PC AT 486 ou supérieur, le système d'exploitation Windows 95/98/NT.

Voyons de manière générale comment fonctionne « Algo2000 ».

Dans le menu du programme, sélectionnez l'élément Interprète et indiquez avec quelle machine nous voulons travailler (dans notre cas, il s’agit d’une « machine de Turing »).

Un champ de machine de Turing apparaîtra devant nous.

Vous devez maintenant définir l'alphabet externe, c'est-à-dire en ligne Alphabet externe indiquer quels caractères y sont inclus (si la chaîne Alphabet externe non visible, vous devez sélectionner un élément de menu Voir | Alphabet externe). Chaque caractère ne peut être spécifié qu'une seule fois. Après avoir fini de saisir l'alphabet externe, la première colonne du tableau est formée : elle est remplie de caractères de l'alphabet externe dans le même ordre. Lors de l'édition de l'alphabet externe, le tableau est automatiquement modifié : des lignes sont insérées, supprimées ou échangées.

N'oublions pas que vous devez d'une manière ou d'une autre disposer les symboles de l'alphabet externe en sections de la bande (vous pouvez laisser toutes les sections vides) et placer le chariot en face de l'une des sections, c'est-à-dire vous devez définir le programme et un certain état de la machine.

Vous pouvez maintenant passer directement à l’écriture de l’algorithme permettant de résoudre le problème. Elle est précisée sous forme de tableau : les caractères de l'alphabet interne sont inscrits dans chaque colonne de la ligne supérieure, et les caractères de l'alphabet externe sont inscrits dans chaque ligne de la première colonne. Les commandes sont placées dans les cellules à l'intersection d'autres colonnes et lignes. Si à l'intersection d'une ligne et d'une colonne nous obtenons une cellule vide, cela signifie que dans cet état interne, ce symbole est introuvable.

Par exemple, nous créons un algorithme pour trouver la différence entre deux entiers positifs (dans le système de nombres décimaux), si l'on sait que le premier nombre est supérieur au second et qu'il y a un signe moins entre eux.

Le champ du programme ressemblera à ceci :

Le format de commande dans chaque cellule est aKq. Ici:
a est le nouveau contenu de la cellule actuelle (un nouveau symbole de l'alphabet externe qui est entré dans la cellule actuelle), K est la commande du mécanisme de bande de la machine de Turing (gauche, droite, stop), q est le nouvel état interne de la machine de Turing.

Le bouton lancera le programme. Si l'exécution n'a pas été suspendue, elle repart toujours de l'état interne Q0 nul.

Le programme peut être complété étape par étape. Pour ce faire, cliquez sur le bouton de la barre d'outils (si les boutons ne sont pas visibles, vous devez sélectionner l'élément de menu Voir | Barre d'outils) ou sélectionnez dans le menu principal Démarrer | Pas à pas. Si vous devez interrompre complètement l'exécution du programme, cela peut être fait en utilisant le bouton de la barre d'outils ou en utilisant le menu principal ( Démarrer | Avorter). Élément du menu Vitesse vous permet d'ajuster la vitesse d'exécution du programme.

Le programme continuera à s'exécuter jusqu'à ce que la commande « Stop » soit rencontrée ou qu'une erreur se produise.

Si vous avez des questions lors de l'utilisation du programme d'interprétation, veuillez vous référer au fichier d'aide. Algo2000.hlp. Celui-ci, ainsi que le programme « Algo2000 » lui-même, sont disponibles sur le site Internet du journal « Informatique » http://inf.1september.ru dans la rubrique « Télécharger ».

Intelligence artificielle (AI, anglais : Intelligence artificielle, IA) - la science et la technologie de création de machines intelligentes, en particulier de programmes informatiques intelligents. L’IA est liée à la tâche similaire consistant à utiliser des ordinateurs pour comprendre l’intelligence humaine, mais ne se limite pas nécessairement à des méthodes biologiquement plausibles.

Qu'est-ce que l'intelligence artificielle

Intelligence(du lat. intellectus - sensation, perception, compréhension, compréhension, concept, raison), ou esprit - une qualité du psychisme consistant en la capacité de s'adapter à de nouvelles situations, la capacité d'apprendre et de se souvenir sur la base de l'expérience, de comprendre et d'appliquer concepts abstraits et utiliser ses connaissances pour la gestion de l'environnement. L'intelligence est la capacité générale de cognition et de résolution de difficultés, qui unit toutes les capacités cognitives humaines : sensation, perception, mémoire, représentation, pensée, imagination.

Au début des années 1980. Les informaticiens Barr et Fajgenbaum ont proposé la définition suivante de l'intelligence artificielle (IA) :

Plus tard, un certain nombre d'algorithmes et de systèmes logiciels ont commencé à être classés comme IA, dont la propriété distinctive est qu'ils peuvent résoudre certains problèmes de la même manière que le ferait une personne réfléchissant à sa solution.

Les principales propriétés de l’IA sont la compréhension du langage, l’apprentissage et la capacité de penser et, surtout, d’agir.

L'IA est un complexe de technologies et de processus connexes qui se développent qualitativement et rapidement, par exemple :

• traitement de texte en langage naturel
• systèmes experts
• agents virtuels (chatbots et assistants virtuels)
• systèmes de recommandation.

Stratégie nationale pour le développement de l'intelligence artificielle

• Article principal : Stratégie nationale pour le développement de l'intelligence artificielle

Recherche sur l'IA

• Article principal : Recherche sur l'intelligence artificielle

Standardisation en IA

2019 : les experts ISO/CEI soutiennent la proposition d'élaborer une norme en russe

Le 16 avril 2019, on a appris que le sous-comité ISO/CEI de normalisation dans le domaine de l'intelligence artificielle soutenait la proposition du comité technique « Systèmes cyber-physiques », créé sur la base du RVC, pour développer « l'intelligence artificielle ». standard. Concepts et terminologie" en russe en plus de la version anglaise de base.

Norme terminologique « Intelligence artificielle. Concepts et terminologie » est fondamental pour toute la famille des documents réglementaires et techniques internationaux dans le domaine de l'intelligence artificielle. Outre les termes et définitions, ce document contient des approches conceptuelles et des principes pour la construction de systèmes avec des éléments, une description de la relation entre l'IA et d'autres technologies de bout en bout, ainsi que des principes de base et des approches-cadres pour la réglementation réglementaire et technique. de l'intelligence artificielle.

À la suite de la réunion du sous-comité ISO/CEI concerné à Dublin, les experts ISO/CEI ont soutenu la proposition de la délégation russe de développer simultanément une norme terminologique dans le domaine de l'IA, non seulement en anglais, mais également en russe. Le document devrait être approuvé début 2021.

Au cours de la réunion, les experts de l'ISO/CEI ont également soutenu l'élaboration d'un projet de document international Technologies de l'information - Intelligence artificielle (IA) - Aperçu des approches informatiques pour les systèmes d'IA, dont la Russie est co-éditeur. Le document donne un aperçu de l'état actuel des systèmes d'intelligence artificielle, décrivant les principales caractéristiques des systèmes, des algorithmes et des approches, ainsi que des exemples d'applications spécialisées dans le domaine de l'IA. L'élaboration de ce projet de document sera réalisée par un groupe de travail 5 spécialement créé « Approches informatiques et caractéristiques informatiques des systèmes d'IA » au sein du sous-comité (SC 42 Groupe de travail 5 « Approches informatiques et caractéristiques informatiques des systèmes d'IA »).

Les technologies d’intelligence artificielle sont très demandées dans divers secteurs de l’économie numérique. Parmi les principaux facteurs entravant leur utilisation pratique à grande échelle figure le sous-développement du cadre réglementaire. Dans le même temps, c'est un cadre réglementaire et technique bien développé qui garantit la qualité spécifiée de l'application technologique et l'effet économique correspondant.

Dans le domaine de l'intelligence artificielle, TC Cyber-Physical Systems, basé sur RVC, élabore un certain nombre de normes nationales dont l'approbation est prévue fin 2019 - début 2020. En outre, des travaux sont en cours avec les acteurs du marché pour formuler un plan national de normalisation (NSP) pour 2020 et au-delà. Le TC « Systèmes cyber-physiques » est ouvert aux propositions d'élaboration de documents des organisations intéressées.

2018 : Élaboration de standards dans le domaine des communications quantiques, de l'IA et de la ville intelligente

Le 6 décembre 2018, le comité technique « Systèmes cyber-physiques » basé sur RVC, en collaboration avec le Centre régional d'ingénierie « SafeNet », a commencé à développer un ensemble de normes pour les marchés de l'Initiative technologique nationale (NTI) et de l'économie numérique. D'ici mars 2019, il est prévu d'élaborer des documents de normalisation technique dans le domaine des communications quantiques, a rapporté RVC. En savoir plus.

Impact de l'intelligence artificielle

Risque pour le développement de la civilisation humaine

Impact sur l'économie et les entreprises

• L’impact des technologies d’intelligence artificielle sur l’économie et les entreprises

Impact sur le marché du travail

Biais de l’intelligence artificielle

Au cœur de tout ce qui constitue la pratique de l’IA (traduction automatique, reconnaissance vocale, traitement du langage naturel, vision par ordinateur, conduite automatisée et bien plus encore) se trouve l’apprentissage profond. Il s’agit d’un sous-ensemble de l’apprentissage automatique, caractérisé par l’utilisation de modèles de réseaux neuronaux, dont on peut dire qu’ils imitent le fonctionnement du cerveau, il serait donc exagéré de les classer dans la catégorie de l’IA. Tout modèle de réseau neuronal est formé sur de grands ensembles de données, il acquiert donc certaines « compétences », mais la manière dont il les utilise reste floue pour ses créateurs, ce qui devient finalement l'un des problèmes les plus importants pour de nombreuses applications d'apprentissage profond. La raison en est qu’un tel modèle fonctionne avec des images de manière formelle, sans aucune compréhension de ce qu’il fait. Un tel système est-il IA et peut-on faire confiance aux systèmes construits sur l’apprentissage automatique ? Les implications de la réponse à la dernière question s’étendent au-delà du laboratoire scientifique. Par conséquent, l’attention des médias sur le phénomène appelé biais de l’IA s’est sensiblement intensifiée. Il peut être traduit par « biais IA » ou « biais IA ». En savoir plus.

Marché des technologies d’intelligence artificielle

Le marché de l'IA en Russie

Marché mondial de l'IA

Domaines d'application de l'IA

Les domaines d'application de l'IA sont assez larges et couvrent à la fois des technologies familières et de nouveaux domaines émergents qui sont loin d'être une application de masse, c'est-à-dire toute la gamme des solutions, des aspirateurs aux stations spatiales. Vous pouvez diviser toute leur diversité selon le critère des points clés de développement.

L’IA n’est pas un domaine monolithique. En outre, certains domaines technologiques de l’IA apparaissent comme de nouveaux sous-secteurs de l’économie et des entités distinctes, tout en servant simultanément la plupart des domaines de l’économie.

Le développement de l’usage de l’IA conduit à l’adaptation des technologies dans les secteurs classiques de l’économie tout au long de la chaîne de valeur et à les transformer, conduisant à l’algorithmisation de presque toutes les fonctionnalités, de la logistique à la gestion d’entreprise.

Utiliser l'IA pour la défense et les affaires militaires

Utilisation dans l'éducation

Utiliser l'IA en entreprise

L'IA dans la lutte contre la fraude

Le 11 juillet 2019, on a appris que dans deux ans seulement, l’intelligence artificielle et l’apprentissage automatique seraient trois fois plus utilisés pour lutter contre la fraude qu’en juillet 2019. Ces données ont été obtenues lors d’une étude conjointe de SAS et de l’Association of Certified Fraud Examiners (ACFE). En juillet 2019, de tels outils antifraude étaient déjà utilisés dans 13 % des organisations ayant participé à l'enquête, et 25 % supplémentaires ont déclaré qu'elles prévoyaient de les mettre en œuvre d'ici un an ou deux. En savoir plus.

L'IA dans l'industrie de l'énergie électrique

• Au niveau de la conception : amélioration de la prévision de la production et de la demande de ressources énergétiques, évaluation de la fiabilité des équipements de production d'électricité, automatisation de l'augmentation de la production lorsque la demande augmente.
• Au niveau de la production : optimisation de la maintenance préventive des équipements, augmentation de l'efficacité de la production, réduction des pertes, prévention du vol des ressources énergétiques.
• Au niveau des promotions : optimisation de la tarification en fonction du moment de la journée et facturation dynamique.
• Au niveau de la prestation de service : sélection automatique du fournisseur le plus rentable, statistiques de consommation détaillées, service client automatisé, optimisation de la consommation énergétique prenant en compte les habitudes et le comportement du client.

L'IA dans l'industrie manufacturière

• Au niveau de la conception : augmentation de l'efficacité du développement de nouveaux produits, évaluation automatisée des fournisseurs et analyse des besoins en pièces de rechange.
• Au niveau de la production : améliorer le processus de réalisation des tâches, automatiser les chaînes de montage, réduire le nombre d'erreurs, réduire les délais de livraison des matières premières.
• Au niveau des promotions : prévision du volume des prestations de support et de maintenance, gestion des tarifs.
• Au niveau de la prestation de services : amélioration de la planification des itinéraires du parc de véhicules, de la demande en ressources du parc, amélioration de la qualité de la formation des ingénieurs de service.

L'IA dans les banques

• Reconnaissance de formes - utilisé incl. reconnaître les clients en agence et leur proposer des offres spécialisées.

L'IA dans les transports

• L'industrie automobile est à l'aube d'une révolution : 5 défis de l'ère de la conduite sans pilote

L'IA en logistique

L'IA dans le brassage

L'IA dans le système judiciaire

Les développements dans le domaine de l’intelligence artificielle contribueront à changer radicalement le système judiciaire, en le rendant plus équitable et exempt de stratagèmes de corruption. Cette opinion a été exprimée à l'été 2017 par Vladimir Krylov, docteur en sciences techniques, consultant technique chez Artezio.

Le scientifique estime que les solutions existantes dans le domaine de l'IA peuvent être appliquées avec succès dans diverses sphères de l'économie et de la vie publique. L’expert souligne que l’IA est utilisée avec succès en médecine, mais qu’à l’avenir, elle pourrait complètement changer le système judiciaire.

« En regardant chaque jour les informations sur les développements dans le domaine de l’IA, on est tout simplement étonné de l’imagination inépuisable et de la fécondité des chercheurs et des développeurs dans ce domaine. Les rapports sur la recherche scientifique sont constamment entrecoupés de publications sur les nouveaux produits qui arrivent sur le marché et de rapports sur les résultats étonnants obtenus grâce à l'utilisation de l'IA dans divers domaines. Si nous parlons d’événements attendus, accompagnés d’un battage médiatique notable, dans lesquels l’IA redeviendra le héros de l’actualité, alors je ne risquerai probablement pas de faire des prévisions technologiques. J’imagine que le prochain événement sera l’émergence quelque part d’un tribunal extrêmement compétent sous forme d’intelligence artificielle, juste et incorruptible. Cela se produira apparemment en 2020-2025. Et les processus qui se dérouleront dans ce tribunal susciteront des réflexions inattendues et le désir de nombreuses personnes de transférer à l’IA la plupart des processus de gestion de la société humaine.

Le scientifique reconnaît l’utilisation de l’intelligence artificielle dans le système judiciaire comme une « étape logique » pour développer l’égalité et la justice législatives. L'intelligence artificielle n'est pas sujette à la corruption et aux émotions, peut adhérer strictement au cadre législatif et prendre des décisions en tenant compte de nombreux facteurs, notamment des données qui caractérisent les parties en conflit. Par analogie avec le domaine médical, les juges robots peuvent opérer avec des mégadonnées provenant de référentiels de services gouvernementaux. On peut supposer que

Musique

Peinture

En 2015, l’équipe de Google a testé les réseaux de neurones pour voir s’ils pouvaient créer eux-mêmes des images. Ensuite, l’intelligence artificielle a été entraînée à l’aide d’un grand nombre d’images différentes. Cependant, lorsqu’on a « demandé » à la machine de représenter quelque chose par elle-même, il s’est avéré qu’elle interprétait le monde qui nous entoure d’une manière quelque peu étrange. Par exemple, pour dessiner des haltères, les développeurs ont reçu une image dans laquelle le métal était relié par des mains humaines. Cela est probablement dû au fait que pendant la phase d'entraînement, les images analysées avec des haltères contenaient des mains, ce que le réseau neuronal a mal interprété.

Le 26 février 2016, lors d'une vente aux enchères spéciale à San Francisco, les représentants de Google ont récolté environ 98 000 dollars grâce à des peintures psychédéliques créées par l'intelligence artificielle. Ces fonds ont été reversés à des œuvres caritatives. L'une des photos les plus réussies de la voiture est présentée ci-dessous.

Un tableau peint par l'intelligence artificielle de Google.

Nous le voyons tout le temps. « RESTful » ceci, « REST » protocole cela, etc. Cependant, beaucoup d’entre nous ne comprennent pas vraiment ce que cela signifie. Nous allons combler exactement cette lacune dans cet article !

État

En informatique (et en mathématiques, dans une certaine mesure), il existe une notion d’État. Un certain système peut être dans l'état UN ou il peut être en état B ou il peut s'agir d'un groupe d'autres états (généralement une liste finie d'états).

À titre d'exemple, disons que vous écrivez un programme qui rend l'écran rouge si la température est supérieure à 80 degrés farenheit ou le rend bleu si la température est inférieure à 80 degrés farenheit.

On peut appeler le premier état (temp > 80 degrés) l’état « A » et le deuxième état (temp< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

C'est l'idée générale de l'État. Voici la définition donnée par Wikipédia :

"En informatique et en théorie des automates, l'état d'un circuit logique numérique ou d'un programme informatique est un terme technique désignant toutes les informations stockées, à un moment donné, qui sont utilisées par le circuit ou le programme."

En bref, c'est une sorte de « combinaison » de toutes les informations prises en compte par le programme.

Maintenant, nous allons faire un saut dans quelque chose qui est considéré comme largement théorique et inutile, puis nous connecter d’une manière ou d’une autre au monde très pratique de REST.

Machines de Turing

Il y avait cet homme nommé Alan Turing, et c'était un mathématicien plutôt intelligent qui s'intéressait au fonctionnement des ordinateurs. Il a conçu un ordinateur imaginaire (qui, comme nous le verrons, est en réalité impossible à construire) qu'il a utilisé pour raisonner sur des choses qui se produisent dans des ordinateurs réels.

L'ordinateur est constitué d'une bande d'une longueur infinie, avec une tête à travers laquelle passe la bande. La bande comporte des « cellules » dans lesquelles des informations peuvent être écrites (chiffres, couleurs, etc.). La bande se déplace dans cette machine, à gauche ou à droite, une cellule à la fois. La machine scanne tout ce qui se trouve déjà sur la bande et, en fonction de l'état dans lequel elle se trouve, elle réécrit quelque chose sur la bande puis change ensuite d'état.

Vous voudrez peut-être relire cette définition pour qu’elle soit complètement intégrée. L'essence de l'idée est qu'elle effectue des opérations sur la mémoire basées sur l'état et les changements d'état en fonction des opérations sur la mémoire.

Cela semble être un fantasme théorique assez inutile (même s’il n’y a absolument rien de mal à cela, lisez Les excuses d’un mathématicien si vous vous demandez pourquoi les gens s’intéressent aux choses théoriques). Cependant, il s’agit probablement du concept le plus fondamental de l’informatique.

Grâce à la machine de Turing, les informaticiens sont capables de raisonner sur n’importe quel algorithme pouvant être exécuté sur un ordinateur. En fait, la machine de Turing a permis de nombreux progrès en informatique.

Ainsi, la machine de Turing nous montre qu’aujourd’hui (remarque : je n’envisage pas les processeurs de réduction de graphes), littéralement tout en informatique est basé sur l’idée d’état.

Le réseau

Puis est apparu le concept d’Internet. C'est un endroit où les paquets peuvent se détraquer et sont renvoyés jusqu'à ce qu'ils atteignent leur destination. En général, il n’y a jamais de transmission complète de données complètes.

Les clients entrent vite et repartent deux fois plus vite. En tant que tel, conserver l’état du client n’a pas beaucoup de sens lorsque l’on travaille sur un système réseau.

De plus, en général, conserver trop d'état dans un système a été une cause de problèmes majeurs (ce qui conduit également à des langages de programmation fonctionnels, qui ne permettent pas de conserver un état dans une grande partie de votre code).

Désormais, les gens avaient besoin d'un protocole réseau pour Internet qui soit simple, rapide et qui gère bien la gestion de l'État dans un environnement extrêmement dynamique.

Ce protocole était HTTP, et la théorie issue des travaux sur HTTP était appelée REST.

REPOS

REST signifie : REpresentational State Transfer. Il s'agit d'un système construit autour du concept « client-serveur » sur lequel les réseaux sont construits (enfin, il existe également des réseaux de type peer to peer, mais le client-serveur est sans doute l'architecture la plus simple et la plus testée). Le nom lui-même est légèrement trompeur, puisque le serveur est totalement sans état !

Il y a quelques contraintes que tous les systèmes qui prétendent être « RESTful » doivent respecter.

Tout d'abord, il doitêtre un système client-serveur. Cette contrainte a été modifiée dans le passé, mais dans la définition formelle (et, pour que la théorie REST fonctionne correctement), nous avons des serveurs auxquels les clients peuvent se connecter.

Le serveur est entièrement apatride. Cela signifie que pour chaque requête client au serveur, aucun état n'est réservé sur le serveur. Par exemple, si un client (utilisant HTTP) demande la page d'index et demande ensuite la page /user/home, les deux requêtes sont complètement indépendantes l'une de l'autre. Le client détient tous de l'état du système (d'où le bouton retour).

Les réponses du serveur doivent pouvoir être mises en cache, ce qui signifie qu'il doit y avoir un système sur le serveur qui identifie les réponses comme pouvant être mises en cache ou non, afin que les clients (par exemple les navigateurs Web) puissent profiter du cache.

Enfin, nous devons avoir une interface simple, propre et uniforme. Si vous avez une certaine expérience du fonctionnement de HTTP, les formulaires de demande sont très simples. Il s'agit en grande partie de verbes et de noms avec un format très facile à analyser et lisible par l'homme. SOAP est une autre forme de protocole réseau qui supprime absolument cette exigence et est donc souvent très difficile à utiliser.

Maintenant, qu’impliquent toutes ces propriétés, prises ensemble ?

Implications du REST

Ils nous permettent de créer des systèmes clairement séparés, évolutifs et débogués facilement.

Considérons d'abord la restriction de l'apatridie sur le serveur, elle pourrait bien être le bit le plus important (et, aussi, le plus souvent violé par les architectures dites RESTful).

Comme mentionné précédemment, dans une architecture client-serveur, les clients sont très agiles ; ils lancent des requêtes et tuent soudainement toute communication. Dans ce genre de situation, il est beaucoup plus propre de ne pas enregistrer l'état du client sur le serveur. Cela nous permet de raisonner très facilement sur les serveurs HTTP ; chaque demande d’un client peut être traitée comme s’il s’agissait d’un tout nouveau client, et cela ne ferait aucune différence.

Deuxièmement, les réponses pouvant être mises en cache signifient que les clients peuvent obtenir des données beaucoup plus rapidement, car les données peuvent souvent être récupérées de la mémoire du client. Cela augmente immédiatement les performances du client et, dans certains systèmes, l'évolutivité du serveur.

L’interface uniforme est peut-être la plus importante. Ayant travaillé avec SOAP, je peux vous dire que le format simple de HTTP est une bénédiction lorsque l'on essaie de déboguer le code du serveur et il en va de même pour d'autres systèmes RESTful.

Concevoir un système RESTful

Disons que nous devons écrire un serveur qui renvoie les cotations boursières, ainsi que conserver une liste de cotations boursières à surveiller (et l'utilisateur peut ajouter ou effacer la liste).

C'est un excellent cas pour un système RESTful, car il est intrinsèquement indépendant de l'identité du client. Par conséquent, le serveur n’a pas besoin de détenir d’état sur le client.

On commence d’abord par définir comment va fonctionner le langage protocolaire (un peu à la manière des verbes GET et POST de HTTP) :

OBTENIR UN DEVIS téléscripteur- donne le prix d'un titre particulier
ADDTICKER téléscripteur- ajoute le stock donné à la liste
GETLIST - obtient une liste d'actions séparées par des virgules dans la liste

C’est un protocole assez simple et ne contient aucun état sur le serveur. Maintenant, en ce qui concerne la mise en cache, nous pouvons dire que nous mettons à jour les prix toutes les heures, donc les caches datant de plus d'une heure peuvent être jetés.

Et c’est tout ce qu’il y a à faire ! Bien sûr, il nous reste encore à mettre en œuvre cela, mais, l'idée générale du système est assez simple et propre !

Conclusion

Espérons que cet article vous a donné une solide compréhension de REST.

J’espère aussi que vous pourrez désormais dénoncer les personnes qui utilisent trop le terme « RESTful » – je peux vous le dire, il y en a beaucoup !

TURING

TURING(Turing) Alan (1912-54), mathématicien et logicien anglais qui a formulé des théories qui deviendront plus tard la base de la technologie informatique. En 1937, il propose Machine de Turing - une machine hypothétique capable de transformer un ensemble de commandes d’entrée. C'était le précurseur des ordinateurs modernes. Turing a également utilisé l'idée d'un ordinateur pour donner une preuve alternative et plus simple du théorème d'incomplétude de Gödel. Turing a joué un rôle majeur dans la résolution d'Enigma, une méthode de cryptage complexe utilisée par l'Allemagne pendant la Seconde Guerre mondiale. En 1948, il participe à la création de l'un des premiers ordinateurs au monde. En 1950, il inventa Test de Turing - c'était censé être un test de la capacité d'un ordinateur à « penser ». Essentiellement, il stipulait qu'une personne ne serait pas capable de distinguer un dialogue avec une machine d'un dialogue avec une autre personne. Ce travail a ouvert la voie à la création de l’INTELLIGENCE ARTIFICIELLE. Turing était également impliqué dans la biologie théorique. En cours "Bases chimiques de la morphogenèse"(1952), il a proposé un modèle décrivant l'origine des différents modèles structurels des organismes en biologie. Depuis, de tels modèles ont souvent été utilisés pour décrire et expliquer de nombreux systèmes observés dans la nature. Turing s'est suicidé après avoir été officiellement accusé d'homosexualité.

Dictionnaire encyclopédique scientifique et technique.

Voyez ce qu'est « TURING » dans d'autres dictionnaires :

Turing, Alan Mathison Alan Turing Alan Mathison Turing Monument dans le parc Sackville Date de naissance ... Wikipedia

- (Turing) Alan Mathieson (1912 54), mathématicien anglais. En 1936-1937, il introduisit le concept mathématique d'un équivalent abstrait d'un algorithme, ou d'une fonction calculable, qui s'appelait alors la machine de Turing... Encyclopédie moderne

- (Turing), Alan Matheson (23 juin 1912 - 7 juin 1954) - Anglais. logicien et mathématicien. En 1936-1937, il proposa un modèle de calcul machine idéalisé. processus - un schéma informatique proche des actions de la personne effectuant les calculs, et mis en avant... ... Encyclopédie philosophique

Turing A.- Turing A. mathématicien anglais. Sujets sécurité de l'information FR Turing… Guide du traducteur technique

Alan Turing Monument Alan Turing à Sackville Park Date de naissance : 23 juin 1912 Lieu de naissance : Londres, Angleterre Date de décès : 7 juin 1954 ... Wikipedia

Turing- Le mathématicien anglais Alan M. Turing, l'un des créateurs des fondements logiques de la technologie informatique, a notamment donné l'une des définitions formelles de l'algorithme ; a prouvé qu'il existe une classe d'ordinateurs capables de simuler... ... Le Monde de Lem - Dictionnaire et Guide

- (Turing) Alan Mathieson (23.6.1912, Londres, 7.6.1954, Wilmslow, près de Manchester), mathématicien anglais. Membre de la Royal Society (1951). Après avoir obtenu son diplôme de l'Université de Cambridge (1935), il rédige sa thèse de doctorat à Princeton... ... Grande Encyclopédie Soviétique

Turing A.M.- TURING (Turing) Alan Mathieson (191254), anglais. mathématicien. Basique tr. en mathématiques logique, calcule. mathématiques. En 193637, il introduisit les mathématiques. le concept d'un équivalent abstrait d'un algorithme, ou d'une fonction calculable, alors appelé. Chariot... Dictionnaire biographique

- (complet Alan Mathison Turing) (23 juin 1912, Londres 7 juin 1954, Wilmslow, Royaume-Uni), mathématicien britannique, auteur d'ouvrages sur la logique mathématique et les mathématiques computationnelles. En 1936-1937, il introduit le concept mathématique... Dictionnaire encyclopédique

Livres

• Une machine peut-elle penser ? Théorie générale et logique des automates. Numéro 14, Turing A., Ce livre, contenant les travaux d'Alan Turing et de John von Neumann, qui furent à l'origine de la création des premiers ordinateurs pensants, appartient aux classiques de la philosophie-cybernétique... Catégorie : Bases de données Série : Sciences artificielles Éditeur : URSS, Fabricant : URSS,
• Une machine peut-elle penser ? Théorie générale et logique des automates. Numéro 14, Turing A., Ce livre, contenant les travaux d'Alan Turing et de John von Neumann, qui furent à l'origine de la création des premières « machines pensantes » d'ordinateurs, appartient aux classiques de la philosophie philosophico-cybernétique. direction... Catégorie :