Les machines Turing supposent-elles quelque chose d'infini à un moment donné?

Dans une question précédente Qu'est-ce qu'un algorithme exactement? , J'ai demandé si avoir un "algorithme" qui renvoie la valeur d'une fonction basée sur un tableau de valeurs précalculées était un algorithme.

L'une des réponses qui a retenu mon attention est celle-ci:

L'exemple factoriel entre dans un modèle de calcul différent, appelé calcul non uniforme. Une machine de Turing est un exemple de modèle de calcul uniforme: elle a une description unique et finie et fonctionne pour des entrées de taille arbitrairement grande. En d'autres termes, il existe une MT qui résout le problème pour toutes les tailles d'entrée.

Maintenant, nous pourrions plutôt considérer le calcul comme suit: Pour chaque taille d'entrée, il existe une MT (ou un autre dispositif de calcul) qui résout le problème. C'est une question très différente. Notez qu'une seule MT ne peut pas stocker la factorielle de chaque entier, car la TM a une description finie. Cependant, nous pouvons créer une MT (ou un programme en C) qui stocke les factorielles de tous les nombres inférieurs à 1000. Ensuite, nous pouvons créer un programme qui stocke les factorielles de tous les nombres entre 1000 et 10000. Et ainsi de suite.

Chaque MT ne suppose-t-elle pas réellement un moyen de gérer l'infini? Je veux dire, même un TM avec une description finie qui calcule la factorielle de tout nombre N à travers l'algorithme

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

contient l'hypothèse qu'un TM a le "matériel" pour comparer des nombres de taille arbitraire via le comparateur "<=", et aussi des ADDers pour incrémenter i jusqu'à un nombre arbitraire, en outre , la capacité de représenter des nombres de taille arbitraire.

Suis-je en train de manquer quelque chose? Pourquoi l'approche que j'ai présentée dans mon autre question est-elle moins réalisable par rapport à l'infini que celle-ci?

Une machine de Turing n'a pas la capacité "de comparer des nombres de taille arbitraire<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

Les machines de Turing ne "traitent pas vraiment de l'infini": elles traitent de choses finies illimitées, du moins dans leur définition standard. L'entrée est une chaîne finie et, après un nombre fini d'étapes, la machine n'a examiné ou écrit que sur un nombre fini de cellules de bande. Il n'y a pas de limite sur la taille de l'entrée ou le nombre d'étapes de calcul, mais l'entrée est finie et, après un nombre fini d'étapes, seule une quantité finie de sortie a été produite.

Je pense que la distinction importante à faire est que la description de la machine de Turing est finie, tout comme l'entrée de la machine, tandis que la bande qu'elle utilise comme mémoire est infinie. Le TM est une machine essentiellement finie, qui utilise une bande finie. Considérez que la bande est composée de cellules, où chaque cellule peut contenir une seule valeur. L'entrée de la MT est écrite sur la bande.

La description d'une MT est un ensemble fini de tuples <current state, input, output, move, next state> .

À chaque étape, la chose à faire est trouvée en faisant correspondre l'état actuel et l'entrée. Par exemple, nous sommes dans l'état 0, et nous lisons un 1, donc nous trouvons le tuple qui commence<0, 1, ...> puis nous écrivons une nouvelle valeur dans la cellule actuelle, nous déplaçons à gauche ou à droite (je pense que la définition classique permet également de rester dans la même cellule ainsi), puis passez à un nouvel état.

Donc, pour votre exemple, vous auriez besoin d'une description infiniment grande de la MT (un nombre infini de <current state, input, output, move, next state> tuples), soit d'inclure les informations de recherche dans l'entrée de la TM. Je crois que l'entrée dans une MT est définie pour être finie. Donc, ce n'est probablement pas quelque chose que vous pourriez faire avec une machine de Turing définie de manière classique.

L'exemple de Fibonacci, en revanche, peut être calculé en binaire avec un nombre fini de tuples pour décrire la MT, et possède une entrée finie.

En résumé : Turing Machine peut effectuer des calculs infinis (finement spécifiés) sur des données infinies (finement spécifiées) et produire des résultats infinis (finement spécifiés). L'idée de base est que ces infinis peuvent être définis comme la limite des entités finies, définies d'une manière mathématiquement appropriée. C'est la base de la sémantique mathématique du calcul. Si vous envisagez des programmes plutôt que des machines de Turing, ces programmes peuvent également contenir des structures de données infinies (finement spécifiées). Le cas d'une fonction tabulée factcomme algorithme possible est finalement analysé, sous forme de programme ou de modèle de MT, avec un indice sur la relation avec l'évaluation paresseuse d'objets infinis.

Avec beaucoup plus de détails

En ce qui concerne votre dernière question, une MT ne calcule pas sur des nombres arbitraires, mais sur la représentation symbolique de ces nombres comme de longues chaînes arbitraires (non bornées) de symboles les représentant. Modulo codage correct, il est vrai qu'ils peuvent comparer ou faire de l'arithmétique avec de tels nombres à travers ces représentations.

Mais la question initiale concerne le rôle de l'infini dans les machines de Turing en général.

Une réponse courante à cette question est que les machines de Turing ne traitent jamais de l'infini. Ils sont définis de manière finie, et tout ce qu'ils calculent est calculé en temps fini sur une partie finie de la bande (donc une bande finie plus grande serait suffisante). Ce qui est vrai, c'est que le temps requis pour l'espace de la TM est illimité, ce qui n'est pas la même chose que l'infini.

Par conséquent, toute réponse qui est calculée par une MT pourrait également être calculée par un automate à états finis (FSA), qui est "dans une certaine mesure" une façon d'examiner la tabulation. La difficulté est que certaines tailles d'entrée (il s'agit presque toujours de cela, ne serait-ce que pour lire l'entrée) dépasseront la taille de l'automate. Mais alors, nous pouvons simplement en utiliser un plus gros. Donc, si nous voulons considérer la taille d'entrée illimitée, nous avons besoin d'une séquence infinie de FSA qui peut faire le calcul. En fait, nous pouvons avoir besoin d'une machine à états finis un peu plus complexe que la FSA traditionnelle car il peut y avoir une sortie à calculer (plutôt qu'une réponse oui-non), mais un transducteur à états finis devrait probablement le faire.

Donc, si nous examinons un problème qui a un ensemble infini d'instances, comme le calcul d'un GCD, ou simplement en utilisant des arithmétiques sur des entiers de taille arbitraire, nous voyons que l'infini nous revient par la porte arrière, comme cet infini ensemble de FSA.

$\pi$

Là encore, nous pouvons remplacer cela par une séquence infinie de calculs finis avec des machines finies. Mais trichons-nous?

D'un point de vue physique, c'est le mieux que nous puissions faire. Nous savons seulement comment construire des machines finies, du moins selon l'état actuel de la technique en physique, qui ne devrait pas trop changer sur cette question dans un avenir proche.

Mais comment pouvons-nous gérer ces infinis de manière cohérente et maniable d'un point de vue mathématique.

Lorsque vous considérez un ensemble infini de FSA qui peut en quelque sorte coopérer pour calculer un ensemble infini de réponses, vous ne pouvez pas le faire arbitrairement. Vous avez besoin de quelques garanties pour vous assurer que ce que vous faites est logique. Il est bien connu que vous pouvez construire trivialement n'importe quel ensemble avec une union infinie d'ensembles réguliers, en fait avec une union infinie d'ensembles singleton. Ainsi, envisager des unions arbitraires infinies d'automates sans aucune restriction ne vous mènera nulle part. Vous considérez même dans le même ensemble d'automates qui vous donnent des réponses incohérentes.

Ce que vous voulez vraiment, c'est définir une notion de cohérence. Mais cela nécessite quelques précautions. Supposons que vous utilisez une séquence infinie d'automates pour simuler une MT qui répond oui ou non, ou ne s'arrête pas. Le problème est qu'une FSA s'arrêtera toujours avec une réponse, comme oui ou non. Mais si vous utilisez un FSA qui n'est en fait pas assez grand pour l'entrée choisie, à quoi devrait-il répondre? Oui et non sont réservés aux cas où la FSA a effectivement mis fin au calcul de la MT, et l'utilisation de l'une de ces réponses avec un calcul inachevé ne ferait que semer la confusion. Ce que vous voulez, c'est une réponse qui dit: " désolé, je suis trop petit et je ne peux pas le dire. Essayez avec un plus grand gars de la famille ". En d'autres termes, vous voulez une réponse telle que le débordement , ou vous ne savez pas$\bot$

Vous avez donc besoin d'automates qui ont 3 sortes d'états: acceptant, non acceptant et non défini. Un état indéfini peut être considéré comme un état représentant une partie manquante de l'automate qui force l'arrêt du calcul. Ainsi, lorsque le calcul s'arrête, selon l'état où il s'arrête, vous obtenez la réponse oui , non ou indéfini .

Maintenant, vous voyez que ce que vous voulez, ce sont des séquences infinies d'automates cohérentes . Les deux oui et non sont compatibles avec indéfini , mais oui est non conforme à pas . Ensuite, deux automates sont cohérents lorsqu'ils donnent des réponses cohérentes sur la même entrée.

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

Je ne développerai pas davantage ces aspects théoriques, ce qui est un peu gênant quand on se base sur Turing Machines. Le fait est que ces concepts conduisent à l'idée que les domaines de calcul (qu'il s'agisse de données ou de machines), forment des structures mathématiques telles que des réseaux, dans lesquels un objet infini peut être défini de manière adéquate comme les limites de séquences infiniment croissantes (c'est-à-dire de mieux en mieux définies) de objets finis. Définir les séquences infinies nécessite un peu plus d'appareil et une notion de continuité. C'est fondamentalement le sujet de la théorie sémantique de Dana Scott, et cela donne une vision quelque peu différente des concepts de calculabilité.

Ensuite, les machines de Turing, ou d'autres dispositifs formels qui peuvent faire du "calcul infini" peuvent être définis comme des limites de séquences d'approximations finies des machines, de mieux en mieux définies. Il en va de même pour toutes les données avec lesquelles les machines calculent, qu'elles soient en entrée ou en sortie.

Le document le plus simple que j'ai jamais lu à ce sujet est un ensemble de notes de cours manuscrites de Dana Scott, souvent appelées notes de cours d'Amsterdam. Mais je ne pouvais pas le trouver sur le web. Tout pointeur vers une copie (même incomplète, car j'en ai une partie) serait le bienvenu. Mais vous pouvez consulter d'autres publications anciennes de Scott telles que Outline of a Mathematical Theory of Computation .

Retour à l'exemple initial de la question

Ces concepts d'approximation s'appliquent aussi bien aux données qu'aux programmes. La fonctionfact est définie de manière récursive, ce qui signifie que c'est le point le moins fixe d'une fonction qui peut être utilisé pour calculer une séquence convergeant l'approximation finie de fact. Cette séquence de fonctions finies de plus en plus définies converge vers une entité infinie qui est ce que vous appelez la fonction fact.

fact$\bot$ ( non définie ) lorsque la table n'est pas suffisamment définie (assez grande). L'algorithme de recherche de table doit également être défini par une séquence d'approximations, car il calcule avec une table infinie.

Il est vrai que, si l'on considère le modèle élémentaire de calcul TM, un tel tableau infini ne peut pas être exprimé dans ce formalisme. Cela ne signifie pas que cela n'aurait aucun sens. Une machine de Turing pourrait avoir une deuxième bande qui est censée être initialisée avec les valeurs tabulées de certaines fonctions telles que fact. Elle ne modifie pas la puissance de calcul de la MT, tant que cette fonction est calculable, c'est-à-dire tant que la table peut être initialisée avec un calcul infini d'une autre MT qui peut calculer toutes les paires argument-valeur pour la fonction concernée.

Mais en pratique, vous ne pouvez pas effectuer un calcul infini. Par conséquent, la bonne façon de le faire est de calculer la table paresseusement, c'est-à-dire de ne remplir les entrées qu'en cas de besoin. C'est précisément ce qui se fait avec la mémorisation, c'est la réponse que je vous ai donnée, avec différentes justifications, pour votre question précédente.

L'essentiel de cette réponse est que les machines de Turing peuvent imiter tout ce que nous pouvons programmer, et nous programmons des calculs sur, avec et sur des objets infinis.

Il s'agit d'une deuxième réponse qui se concentre davantage sur la question spécifique posée que sur le cadre théorique général qui justifie la réponse, et serait définitivement nécessaire pour répondre au titre plus général de la question. Il est entièrement compatible avec mes réponses précédentes aux questions du PO, les deux Qu'est-ce qu'un algorithme exactement? et les machines de turing supposent-elles quelque chose d'infini à un moment donné?, réponses dans lesquelles j'ai développé davantage le contexte théorique. Cela peut être considéré comme répondant aux deux questions.

Les machines Turing ont la capacité de traiter l'infini , comme tous les modèles informatiques complets de Turing, mais uniquement avec l'infini dénombrable. Notre problème est que nous ne pouvons observer qu'une partie de cet infini, mais nous devons considérer l'ensemble de celui-ci car la partie que nous pouvons observer est illimitée.

L'autre problème est que nous ne pouvons nous occuper que d'entités finies. En fait, toute la structure de la science telle que nous la connaissons tombe en panne si nous considérons des entités qui ne sont pas finement spécifiées, car il devient impossible de vérifier la cohérence des définitions, même de savoir quelles sont les définitions, car nous ne pouvons accéder qu'à une partie d'entre elles dans un temps fini.

Il y a peut-être un autre problème fondamental qui est quelque peu similaire au fait que la fermeture sous l'union infinie définit tout ensemble que vous voulez, à moins que vous ne puissiez restreindre finement de manière appropriée ce qui est autorisé dans une telle union. Mais je ne suis pas sûr de bien comprendre ce problème.

Comme je l'ai dit, les machines Turing ont la capacité de gérer l'infini . Je contredit d'autres réponses bien votées de certains utilisateurs de haute réputation, qui devraient savoir de quoi ils parlent sur un sujet aussi élémentaire.

Le problème est que Turing a choisi un modèle de calcul très élémentaire pour atteindre son objectif théorique. Plus c'est simple, mieux c'est. C'est à des modèles de calcul plus avancés / sophistiqués à peu près ce qu'est le langage machine à la programmation: quelque chose de très obscur où vous ne pouvez reconnaître aucun des concepts qui ont du sens dans la programmation de haut niveau. Le fait est que, comme le langage machine, la MT peut imiter beaucoup plus qu'elle ne peut l'exprimer directement.

$23{rd}$ Mais il serait toujours souvent implémenté comme un calcul infini qui est artificiellement arrêté lorsque la bonne réponse est obtenue.

En fait, tous les utilisateurs qui déclarent que tout est fini mais sans limite dans une MT sont très prudents pour ajouter qu'ils considèrent les machines de Turing dans leur définition standard . Le problème est que la définition standard n'est qu'un moyen de simplifier la théorie, mais est à peu près hors de propos lorsque l'on essaie de comprendre les structures de calcul.

En fait, la seule chose qui compte dans le calcul est que tout doit être spécifié de manière finie d'une manière calculable, pas qu'il soit fini .

Nous supposons qu'une machine de turing doit être un objet fini. Mais ce n'est pas vrai. Vous pouvez définir un modèle de machine Turing à l'aide d'une deuxième bande qui est en lecture seule et contient une fonction tabulée pour toutes les valeurs entières, sans aucune limite. C'est infini. Mais cela ne vous achète pas de puissance de calcul supplémentaire tant que le contenu de cette bande est spécifié de manière calculable (la calculabilité implique qu'elle est spécifiée de manière finie). La bande supplémentaire pourrait bien être remplacée par une machine TM intégrée dans l'autre, et fournirait les réponses, au lieu de les chercher sur la bande supplémentaire. D'un niveau supérieur, la différence n'est pas visible.

D'un point de vue pratique de réalisation, nous pourrions avoir une fact machine de Turing calculant les factoriels et les tabulant sur la bande supplémentaire, tandis qu'une autre MT utiliserait la factorielle tabulée de la bande supplémentaire, attendant simplement la première TM chaque fois que la tabulation en manque encore entrée. Mais la deuxième machine suppose que le contenu de la bande est finalement infini. La machine de tabulation n'a même pas à fonctionner tout le temps, mais doit reprendre le calcul chaque fois que des données sont demandées dans la table et n'y sont pas trouvées.

Pour revenir à la question, la principale différence entre les entiers non bornés et la table infinie est seulement que les entiers sont finis, non bornés mais entièrement calculés en temps fini. La table infinie est calculée indéfiniment, finie mais toujours en croissance à l'infini. Ce n'est pas un problème, mais c'est une différence. Les objets infinis ne sont accessibles que par approximations finies, ... mais ils sont infinis. Les nombres irrationnels calculables sont, en ce sens, des objets infinis, du moins pour leur représentation sous forme de nombres binaires.

Tous les algorithmes sont définis dans le contexte d'une théorie mathématique. Et une recherche de table avec une table infinie est un algorithme. Mais c'est un algorithme dans une théorie mathématique ayant un ensemble infini défini d'axiomes qui spécifient de manière extensive (plutôt qu'intensivement) les valeurs d'une fonction qu'il axiomatise pour chaque argument entier. (voir ma réponse à votre question précédente ). Ensuite, il est toujours légitime de le faire, car vous pouvez toujours ajouter des déclarations prouvées vraies aux axiomes d'une théorie.

Les déclarations Usul, telles que reproduites dans votre question actuelle, sont à mon avis incorrectes (bien que tout soit également une question de définition). Sa conclusion dans sa réponse , que vous n'avez pas reproduite, est que l'utilisation d'une table infinie ne peut pas être considérée comme un algorithme car elle ne peut être implémentée que par un modèle de calcul non uniforme, par un ensemble de machines différentes, et donc utilise " n'ont pas de description finie qui peut être implémentée pour résoudre le problème" entier "pour n'importe quelle taille d'entrée$\pi$

La façon dont ces entités infinies sont calculées dans la pratique est au moyen d'une évaluation paresseuse , en calculant exactement la partie nécessaire à tout moment et en reprenant le calcul pour une partie du reste chaque fois qu'il en faut plus. C'est exactement ce qui est proposé ci-dessus avec la factmachine calculant paresseusement la factorielle à stocker dans une table, chaque fois que davantage de données sont nécessaires de la table.

D'une certaine manière, cela semble confirmer l'affirmation (dans la réponse de DanielV ) que l'espace de code doit être fini, car l'évaluation paresseuse sera en fait basée sur un code fini. Mais la calculabilité est un jeu de codage omniprésent, de sorte que, entre autres choses, la distinction entre le code et les données est toujours à peu près aux yeux du spectateur. En effet, de nombreux langages de programmation modernes ne font pas beaucoup de différence entre la spécification intensionnelle et extensionnelle des valeurs, et la sémantique dénotationnelle ne distingue pas vraiment "2 + 2" de "4". La sémantique est vraiment ce dont nous parlons lorsque nous posons une question telle que " Qu'est-ce que X ? ".

Cette vue de la finitude du code, également considérée comme statique, est une autre raison pour laquelle une table infinie (considérée comme faisant partie du code) n'est pas vue sur un pied d'égalité avec des entiers non bornés utilisés comme données. Mais c'est une autre illusion qui ne survit pas aux pratiques de programmation connues en métaprogrammation , langages réflexifs et utilisation de la evalfonction. Dans ces langues, le code peut être étendu sans limites par le programme en cours d'exécution lui-même, tant que l'ordinateur est en cours d'exécution. En effet, on pourrait envisager des machines de Turing qui modifient leurs propres règles de transition, en augmentant leur nombre sans limite. C'est assez proche de la façon dont les machines Universal Turing fonctionnent.

Lors de la conception de cadres théoriques, il y a toujours une tension entre la simplicité et la perspicacité ou l'expressivité. La simplicité rend l'analyse du cadre souvent plus simple, surtout lorsqu'il s'agit de prouver des propriétés spécifiques ou de le réduire à d'autres cadres. Mais il est souvent gênant d'exprimer des concepts de haut niveau qui doivent ensuite être encodés. Nous ne programmons pas avec Turing Machines, mais avec des langages de haut niveau qui sont beaucoup plus expressifs et perspicaces, et peuvent en même temps effacer certaines barrières telles que la distinction entre code et données, sur la base de l'équivalence sémantique. Les machines de Turing semblent simples, mais peuvent aller bien au-delà de leur définition élémentaire.

La réponse courte: non . Les machines de Turing ne pas assumer quoi que ce soit infini à tout moment.

C'est une des raisons pour lesquelles ils sont valables comme modèle de calcul. Il n'est pas logique de décrire le calcul comme quelque chose effectué par un appareil infini.

Cependant, leur fonctionnement peut être infini: il peut ne pas se terminer. C'est une autre raison pour laquelle ils sont valides comme modèle de calcul. Les appareils qui ne peuvent effectuer que des opérations dont la terminaison est garantie ne peuvent pas exprimer tous les calculs possibles.

De plus: l'opération nécessite une mémoire illimitée : bien que la quantité réelle de mémoire utilisée soit toujours limitée, elle peut devenir arbitrairement grande. Vous ne pouvez donc pas fournir toute la mémoire dont toute opération aura besoin à l'avance. Les appareils qui ne peuvent effectuer que des opérations qui sont garanties de ne jamais utiliser plus qu'une certaine quantité fixe de mémoire ne peuvent pas exprimer tous les calculs possibles.

"sortir des sentiers battus" et généraliser sur cette question qui touche au cœur de l'abstraction des machines de Turing, et proposer un angle différent qui n'a pas encore été répondu: oui, les machines de Turing ont certains aspects intrinsèques de "supposer les infinis" juste car le concept est intrinsèque aux mathématiques. Les MT sont une abstraction de machines physiques. les concepts physiques du Temps et de l'Espace sont volontairement utilisés dans la théorie de la MT mais comme abstractions, mais aussi avec des aspects de leurs homologues réels.

en bref, la MT peut éventuellement fonctionner indéfiniment en théorie , alias le problème d'arrêt . la bande est infinie, mais seule une quantité finie peut être écrite à un moment donné. une MT qui fonctionne pour toujours suppose fondamentalement que le temps et l'espace sont illimités, c'est-à-dire "infinis". en fait, il existe une hiérarchie / «continuum» de temps et d' espace correspondante qui est infinie.

mais aucune réalisation physique de ce concept abstrait n'est possible en supposant que l'univers physique est borné (espace, temps, matière, dont le dernier est quelque peu analogue aux «symboles» ou «encre» dans la machine de Turing). quelque peu similaire / analogue, en physique, parfois l'univers est considéré comme illimité / infini, mais seulement comme une abstraction. pour inverser cela, c'est aussi pourquoi la "modélisation" d'un ordinateur moderne comme une machine de Turing est elle-même une abstraction, car l'ordinateur ne peut avoir qu'une mémoire finie, etc.

une autre comparaison utile est la droite numérique en mathématiques. la droite numérique est infinie, mais elle dénote des nombres finis. chaque nombre sur la droite numérique représente une quantité finie, mais il existe un nombre infini de ces quantités finies. la bande de machine de Turing a une forte similitude avec le concept de ligne numérique des mathématiques. Turing aurait pu facilement le définir comme seulement infini dans une direction, mais il l'a défini comme infini dans les deux directions, un peu comme la droite numérique mathématique, avec des positions négatives "à gauche" sur la bande et des positions positives "à droite".