Les ordinateurs ont progress\u00e9 \u00e0 pas de g\u00e9ant au cours des derni\u00e8res d\u00e9cennies, mais cela ne signifie pas qu\u2019ils peuvent tout r\u00e9soudre.<\/p>\n
![\"\"](\"https:\/\/yogaesoteric.net\/wp-content\/uploads\/2023\/06\/125012_1-e1687881837550.jpg\")
Gr\u00e2ce aux technologies d\u2019intelligence artificielle, les ordinateurs peuvent aujourd\u2019hui engager des conversations convaincantes avec des personnes, composer des chansons, peindre des tableaux, jouer aux \u00e9checs et au go, et diagnostiquer des maladies, pour ne citer que quelques exemples de leurs prouesses technologiques.<\/p>\n
Ces succ\u00e8s pourraient \u00eatre consid\u00e9r\u00e9s comme une indication que le calcul n\u2019a pas de limites. Pour voir si c\u2019est le cas, il est important de comprendre ce qui rend un ordinateur puissant.<\/p>\n
La puissance d\u2019un ordinateur comporte deux aspects : le nombre d\u2019op\u00e9rations que son mat\u00e9riel peut ex\u00e9cuter par seconde et l\u2019efficacit\u00e9 des algorithmes qu\u2019il ex\u00e9cute. La vitesse du mat\u00e9riel est limit\u00e9e par les lois de la physique. Les algorithmes \u2013 essentiellement des ensembles d\u2019instructions \u2013 sont \u00e9crits par des humains et traduits en une s\u00e9quence d\u2019op\u00e9rations que le mat\u00e9riel informatique peut ex\u00e9cuter. M\u00eame si la vitesse d\u2019un ordinateur pouvait atteindre la limite physique, des obstacles informatiques subsistent en raison des limites des algorithmes.<\/p>\n
Ces obstacles comprennent des probl\u00e8mes impossibles \u00e0 r\u00e9soudre par les ordinateurs et des probl\u00e8mes qui sont th\u00e9oriquement solubles mais qui, en pratique, d\u00e9passent les capacit\u00e9s des ordinateurs actuels, m\u00eame les plus puissants, que l\u2019on puisse imaginer. Les math\u00e9maticiens et les informaticiens tentent de d\u00e9terminer si un probl\u00e8me est soluble en l\u2019essayant sur une machine imaginaire.<\/p>\n
Une machine \u00e0 calculer imaginaire<\/strong><\/p>\n La notion moderne d\u2019algorithme, connue sous le nom de machine de Turing, a \u00e9t\u00e9 formul\u00e9e en 1936 par le math\u00e9maticien britannique Alan Turing. Il s\u2019agit d\u2019un dispositif imaginaire qui imite la fa\u00e7on dont les calculs arithm\u00e9tiques sont effectu\u00e9s avec un crayon sur du papier. La machine de Turing est le mod\u00e8le sur lequel tous les ordinateurs actuels sont bas\u00e9s.<\/p>\n Pour permettre des calculs qui n\u00e9cessiteraient plus de papier s\u2019ils \u00e9taient effectu\u00e9s manuellement, la r\u00e9serve de papier imaginaire d\u2019une machine de Turing est suppos\u00e9e \u00eatre illimit\u00e9e. Cela \u00e9quivaut \u00e0 un ruban imaginaire illimit\u00e9, ou \u00ab bande \u00bb, de carr\u00e9s, dont chacun est soit vide, soit contient un symbole.<\/p>\n La machine est contr\u00f4l\u00e9e par un ensemble fini de r\u00e8gles et d\u00e9marre sur une s\u00e9quence initiale de symboles sur le ruban. Les op\u00e9rations que la machine peut effectuer sont le d\u00e9placement vers une case voisine, l\u2019effacement d\u2019un symbole et l\u2019\u00e9criture d\u2019un symbole sur une case vide. La machine calcule en effectuant une s\u00e9quence de ces op\u00e9rations. Lorsque la machine termine, ou \u00ab s\u2019arr\u00eate \u00bb, les symboles restant sur la bande constituent la sortie ou le r\u00e9sultat.<\/p>\n