Caractérisations d'algorithmes - Algorithm characterizations

Les caractérisations d'algorithmes sont des tentatives de formalisation du mot algorithme . L'algorithme n'a pas de définition formelle généralement acceptée. Les chercheurs travaillent activement sur ce problème. Cet article présentera plus en détail certaines des «caractérisations» de la notion d '«algorithme».

Le problème de la définition

Au cours des 200 dernières années, la définition de l'algorithme est devenue plus compliquée et détaillée à mesure que les chercheurs ont tenté de cerner le terme. En effet, il peut y avoir plus d'un type d '«algorithme». Mais la plupart conviennent que l'algorithme a quelque chose à voir avec la définition de processus généralisés pour la création d'entiers "de sortie" à partir d'autres entiers "d'entrée" - "paramètres d'entrée" arbitraires et d'une étendue infinie, ou limités en étendue mais toujours variables - par la manipulation de symboles distinctifs (compter les nombres) avec des collections finies de règles qu'une personne peut exécuter avec du papier et un crayon.

Les schémas de manipulation des nombres les plus courants - à la fois en mathématiques formelles et dans la vie de routine - sont: (1) les fonctions récursives calculées par une personne avec du papier et un crayon, et (2) la machine de Turing ou ses équivalents de Turing - le registre primitif - modèle de machine ou "contre-machine", le modèle de machine à accès aléatoire (RAM), le modèle de machine à programme stocké à accès aléatoire (RASP) et son équivalent fonctionnel "l' ordinateur ".

Lorsque nous faisons de l '«arithmétique», nous calculons réellement en utilisant des «fonctions récursives» dans les algorithmes de sténographie que nous avons appris à l'école primaire, par exemple, en ajoutant et en soustrayant.

Les preuves que chaque «fonction récursive» que nous pouvons calculer à la main que nous pouvons calculer par machine et vice versa - notez l'utilisation des mots calculer contre calculer - sont remarquables. Mais cette équivalence, associée à la thèse (affirmation non prouvée) selon laquelle cela inclut tous les calculs / calculs, indique pourquoi tant d’accent a été mis sur l’utilisation de machines équivalentes à Turing dans la définition d’algorithmes spécifiques, et pourquoi la définition de «algorithme» lui-même renvoie souvent à «la machine de Turing ». Ceci est discuté plus en détail dans la caractérisation de Stephen Kleene .

Ce qui suit sont des résumés des caractérisations les plus connues (Kleene, Markov, Knuth) ainsi que celles qui introduisent de nouveaux éléments - des éléments qui élargissent davantage la définition ou contribuent à une définition plus précise.

[ Un problème mathématique et son résultat peuvent être considérés comme deux points dans un espace, et la solution consiste en une séquence d'étapes ou un chemin les reliant. La qualité de la solution est fonction du chemin. Il pourrait y avoir plus d'un attribut défini pour le chemin, la longueur par exemple, la complexité de la forme, une facilité de généralisante, la difficulté, et ainsi de suite . ]

Hiérarchie Chomsky

Il y a plus de consensus sur la «caractérisation» de la notion d '«algorithme simple».

Tous les algorithmes doivent être spécifiés dans un langage formel, et la «notion de simplicité» découle de la simplicité du langage. La hiérarchie de Chomsky (1956) est une hiérarchie de confinement de classes de grammaires formelles qui génèrent des langages formels . Il est utilisé pour classer les langages de programmation et les machines abstraites .

Du point de vue de la hiérarchie de Chomsky , si l'algorithme peut être spécifié sur un langage plus simple (que sans restriction), il peut être caractérisé par ce type de langage, sinon c'est un "algorithme sans restriction" typique.

Exemples: un langage de macro "à usage général", comme M4 n'est pas restreint ( Turing complet ), mais le langage de macro de préprocesseur C ne l'est pas, donc tout algorithme exprimé en préprocesseur C est un "algorithme simple".

Voir aussi Relations entre les classes de complexité .

Caractéristiques d'un bon algorithme

Voici les caractéristiques d'un bon algorithme;

  • Précision: un bon algorithme doit avoir certaines étapes décrites. Les étapes doivent être suffisamment exactes et ne pas varier.
  • Unicité: chaque étape prise dans l'algorithme doit donner un résultat défini comme indiqué par l'auteur de l'algorithme. Les résultats ne doivent en aucun cas fluctuer.
  • Faisabilité: l'algorithme doit être possible et réalisable dans la vie réelle. Cela ne doit pas être abstrait ou imaginaire.
  • Entrée: un bon algorithme doit être capable d'accepter un ensemble d'entrées définies.
  • Sortie: un bon algorithme devrait être capable de produire des résultats en sortie, de préférence des solutions.
  • Finitude: l'algorithme doit avoir un arrêt après un certain nombre d'instructions.
  • Généralités: l'algorithme doit s'appliquer à un ensemble d'entrées définies.

1881 La réaction négative de John Venn à la machine logique de W. Stanley Jevons de 1870

Au début de 1870, W. Stanley Jevons présenta une "machine logique" (Jevons 1880: 200) pour analyser un syllogisme ou une autre forme logique, par exemple un argument réduit à une équation booléenne . Au moyen de ce que Couturat (1914) appelait une "sorte de piano logique [,] ... les égalités qui représentent les prémisses ... sont" jouées "sur un clavier comme celui d'une machine à écrire. ... Quand toutes les prémisses ont été "joués", le panneau ne montre que les constituants dont la somme est égale à 1, c'est-à-dire ... son ensemble logique. Cette méthode mécanique a l'avantage sur la méthode géométrique de VENN ... "(Couturat 1914: 75).

De son côté, John Venn , logicien contemporain de Jevons, était loin d'être ravi, estimant qu '"il ne me semble pas que les artifices actuellement connus ou susceptibles d'être découverts méritent vraiment le nom de machines logiques" (italiques ajoutés, Venn 1881: 120). Mais d'une utilité historique à la notion en développement d '«algorithme» est son explication de sa réaction négative à l'égard d'une machine qui «peut servir un objectif vraiment précieux en nous permettant d'éviter un travail autrement inévitable»:

(1) "Il y a d'abord l'énoncé de nos données dans un langage logique précis",
(2) "Ensuite, nous devons jeter ces déclarations dans une forme adaptée au fonctionnement du moteur - dans ce cas, la réduction de chaque proposition à ses dénégations élémentaires",
(3) "Troisièmement, il y a la combinaison ou le traitement ultérieur de nos locaux après une telle réduction,"
(4) "Enfin, les résultats doivent être interprétés ou lus. Cette dernière donne généralement lieu à une grande ouverture à l'habileté et à la sagacité."

Il conclut que "je ne vois pas qu'aucune machine ne puisse espérer nous aider sauf dans la troisième de ces étapes; de sorte qu'il semble très douteux que quelque chose de ce genre mérite vraiment le nom d'un moteur logique." (Venn 1881: 119 –121).

1943, 1952 Caractérisation de Stephen Kleene

Cette section est plus longue et plus détaillée que les autres en raison de son importance pour le sujet: Kleene a été le premier à proposer que tous les calculs / calculs - de toute sorte, la totalité de - puissent être (i) calculés de manière équivalente en utilisant cinq " opérateurs récursifs primitifs "plus un opérateur spécial appelé opérateur mu , ou être (ii) calculé par les actions d'une machine de Turing ou d'un modèle équivalent.

En outre, il a estimé que l'un ou l'autre de ces éléments constituerait une définition d' algorithme .

Un lecteur confrontant d'abord les mots qui suivent peut très bien être confus, donc une brève explication s'impose. Les moyens de calcul sont faits à la main, les moyens de calcul sont effectués par machine de Turing (ou équivalent). (Parfois, un auteur glisse et échange les mots). Une "fonction" peut être considérée comme une "boîte d'entrée-sortie" dans laquelle une personne met des nombres naturels appelés "arguments" ou "paramètres" (mais uniquement les nombres de comptage comprenant 0 - les entiers non négatifs) et en sort un seul non négatif entier (appelé conventionnellement "la réponse"). Pensez à la "boîte de fonctions" comme à un petit homme calculant à la main en utilisant la "récursion générale" ou en calculant par une machine de Turing (ou une machine équivalente).

"Effectivement calculable / calculable" est plus générique et signifie "calculable / calculable par une procédure, une méthode, une technique ... peu importe ...". «Général récursif» était la manière de Kleene d'écrire ce qu'on appelle aujourd'hui simplement «récursivité»; cependant, la «récursion primitive» - calcul à l'aide des cinq opérateurs récursifs - est une forme moindre de récursivité qui n'a pas accès au sixième opérateur mu supplémentaire qui n'est nécessaire que dans de rares cas. Ainsi, la plus grande partie de la vie ne requiert que les «fonctions récursives primitives».

1943 "Thèse I", 1952 "Thèse de l'Église"

En 1943, Kleene proposa ce que l'on appelle désormais la thèse de l'Église :

" Thèse I. Toute fonction effectivement calculable (prédicat effectivement décidable) est récursive générale" (Déclaré pour la première fois par Kleene en 1943 (réimprimé page 274 dans Davis, ed. The Undecidable ; apparaît également textuellement dans Kleene (1952) p.300)

En un mot: pour calculer n'importe quelle fonction, les seules opérations dont une personne a besoin (techniquement, formellement) sont les 6 opérateurs primitifs de récursivité "générale" (aujourd'hui appelés opérateurs des fonctions récursives mu ).

La première déclaration de Kleene à ce sujet était sous le titre de la section " 12. Théories algorithmiques ". Il l'amplifiera plus tard dans son texte (1952) comme suit:

"La thèse I et sa réciproque fournissent la définition exacte de la notion de procédure ou d' algorithme de calcul (décision) , pour le cas d'une fonction (prédicat) d'entiers naturels" (p. 301, gras ajouté pour accentuer)

(Son utilisation des mots «décision» et «prédicat» étend la notion de calculabilité à la manipulation plus générale des symboles, comme cela se produit dans les «preuves» mathématiques.)

Ce n'est pas aussi intimidant que cela puisse paraître - la récursivité "générale" est juste une manière de réaliser nos opérations arithmétiques quotidiennes à partir des cinq "opérateurs" des fonctions récursives primitives avec l' opérateur mu supplémentaire si nécessaire. En effet, Kleene donne 13 exemples de fonctions récursives primitives et Boolos – Burgess – Jeffrey en ajoute d'autres, dont la plupart seront familières au lecteur - par exemple l'addition, la soustraction, la multiplication et la division, l'exponentiation, la fonction CASE, la concaténation, etc., etc.; pour une liste, voir Quelques fonctions récursives primitives courantes .

Pourquoi des fonctions générales récursives plutôt que des fonctions primitives récursives?

Kleene et coll. (cf §55 Fonctions récursives générales p. 270 dans Kleene 1952) a dû ajouter un sixième opérateur de récursivité appelé l'opérateur de minimisation (écrit comme μ-opérateur ou mu-opérateur ) car Ackermann (1925) a produit une fonction extrêmement croissante - l' Ackermann fonction - et Rózsa Péter (1935) a produit une méthode générale de création de fonctions récursives en utilisant l'argument diagonal de Cantor , dont aucun ne pouvait être décrit par les 5 opérateurs de fonction primitive-récursive. En ce qui concerne la fonction Ackermann:

"... dans un certain sens, la longueur de l' algorithme de calcul d'une fonction récursive qui n'est pas aussi récursive primitive croît plus vite avec les arguments que la valeur de toute fonction récursive primitive" (Kleene (1935) réimprimé p. 246 dans The Indécidable , plus la note de bas de page 13 concernant la nécessité d'un opérateur supplémentaire, en gras ajouté).

Mais le besoin de l'opérateur mu est une rareté. Comme indiqué ci-dessus par la liste de calculs courants de Kleene, une personne vaquait à sa vie en calculant joyeusement des fonctions récursives primitives sans craindre de rencontrer les nombres de monstres créés par la fonction d'Ackermann (par exemple la super-exponentiation ).

1952 "Thèse de Turing"

La thèse de Turing émet l'hypothèse de la calculabilité de «toutes les fonctions calculables» par le modèle de machine de Turing et ses équivalents.

Pour ce faire de manière efficace, Kleene a étendu la notion de «calculable» en élargissant le réseau - en admettant dans la notion de «fonctions» à la fois les «fonctions totales» et les «fonctions partielles». Une fonction totale est celle qui est définie pour tous les nombres naturels (entiers positifs comprenant 0). Une fonction partielle est définie pour certains nombres naturels mais pas tous - la spécification de «certains» doit venir «à l'avant». Ainsi l'inclusion de «fonction partielle» étend la notion de fonction aux fonctions «moins parfaites». Les fonctions totales et partielles peuvent être soit calculées à la main, soit calculées par machine.

Exemples:
"Fonctions": inclure "soustraction commune m  -  n " et "addition m  +  n "
"Fonction partielle": "Soustraction commune" m  -  n n'est pas défini lorsque seuls les nombres naturels (entiers positifs et zéro) sont autorisés en entrée - par exemple, 6 - 7 n'est pas défini
Fonction totale: "Addition" m  +  n est défini pour tous les nombres entiers positifs et zéro.


Nous observons maintenant la définition de Kleene de «calculable» dans un sens formel:

Définition: "Une fonction partielle φ est calculable , s'il existe une machine M qui la calcule" (Kleene (1952) p. 360)
"Définition 2.5. Une fonction n -ary f ( x 1 , ..., x n ) est partiellement calculable s'il existe une machine de Turing Z telle que
f ( x 1 , ..., x n ) = Ψ Z ( n ) ( x 1 , ..., [ x n )
Dans ce cas, nous disons que [machine] Z calcule f . Si, en plus, f ( x 1 , ..., x n ) est une fonction totale, alors on l'appelle calculable »(Davis (1958) p. 10)

Ainsi nous sommes arrivés à la thèse de Turing :

"Toute fonction qui serait naturellement considérée comme calculable est calculable ... par l'une de ses machines ..." (Kleene (1952) p.376)

Bien que Kleene n'ait pas donné d'exemples de «fonctions calculables», d'autres l'ont fait. Par exemple, Davis (1958) donne des tables de Turing pour les fonctions Constante, Successeur et Identité, trois des cinq opérateurs des fonctions récursives primitives :

Calculable par la machine de Turing:
Addition (est également la fonction Constante si un opérande est 0)
Incrément (fonction successeur)
Soustraction commune (définie uniquement si x y ). Ainsi " x  -  y " est un exemple de fonction partiellement calculable.
Soustraction correcte x y (telle que définie ci-dessus)
La fonction d'identité: pour chaque i , il existe une fonction U Z n = Ψ Z n ( x 1 , ..., x n ) qui extrait x i de l'ensemble des arguments ( x 1 , ..., x n )
Multiplication

Boolos – Burgess – Jeffrey (2002) donnent les descriptions suivantes en prose des machines de Turing pour:

Doublage: 2 p
Parité
Une addition
Multiplication

En ce qui concerne la machine de comptage , un modèle de machine abstrait équivalent à la machine de Turing:

Exemples calculables par machine Abacus (cf Boolos – Burgess – Jeffrey (2002))
Une addition
Multiplication
Exponention: (un organigramme / un schéma de principe de l'algorithme)

Démonstrations de calculabilité par machine abaque (Boolos – Burgess – Jeffrey (2002)) et par contre machine (Minsky 1967):

Les six opérateurs de fonction récursifs:
  1. Fonction zéro
  2. Fonction successeur
  3. Fonction d'identité
  4. Fonction de composition
  5. Récursivité primitive (induction)
  6. Minimisation

Le fait que les modèles abaque / contre-machine puissent simuler les fonctions récursives fournit la preuve que: Si une fonction est "calculable par machine" alors elle est "calculable à la main par récursion partielle". Théorème XXIX de Kleene:

" Théorème XXIX:" Toute fonction partielle calculable φ est partielle récursive ... "(italique dans l'original, p. 374).

L'inverse apparaît comme son théorème XXVIII. Ensemble, ceux-ci forment la preuve de leur équivalence, le théorème XXX de Kleene.

1952 Thèse Church-Turing

Avec son théorème XXX, Kleene prouve l' équivalence des deux «thèses» - la thèse de l'Église et la thèse de Turing. (Kleene ne peut qu'émettre l'hypothèse (conjecturer) la vérité des deux thèses - il ne les a pas prouvées ):

THÉORÈME XXX: Les classes suivantes de fonctions partielles ... ont les mêmes membres: (a) les fonctions récursives partielles, (b) les fonctions calculables ... " (p. 376)
Définition de "fonction récursive partielle": "Une fonction partielle φ est récursive partielle dans [les fonctions partielles] ψ 1 , ... ψ n s'il existe un système d'équations E qui définit φ récursivement à partir de [fonctions partielles] ψ 1 , ... ψ n "(p. 326)

Ainsi, par le théorème XXX de Kleene: l'une ou l'autre méthode de création de nombres à partir de nombres d'entrée - fonctions récursives calculées à la main ou calculées par la machine de Turing ou équivalent - aboutit à une "fonction effectivement calculable / calculable ". Si nous acceptons l'hypothèse que chaque calcul / calcul peut être fait par l'une ou l'autre méthode de manière équivalente, nous avons accepté à la fois le théorème de Kleene XXX (l'équivalence) et la thèse de Church-Turing (l'hypothèse de «tout»).

Une note de dissidence: "Il y a plus à l'algorithme ..." Blass et Gurevich (2003)

La notion de séparation des thèses de Church et de Turing de la «thèse de Church-Turing» apparaît non seulement dans Kleene (1952) mais aussi dans Blass-Gurevich (2003). Mais s'il y a des accords, il y a aussi des désaccords:

"... nous ne sommes pas d'accord avec Kleene pour dire que la notion d' algorithme est si bien comprise. En fait, la notion d'algorithme est plus riche de nos jours qu'elle ne l'était à l'époque de Turing. Et il existe des algorithmes, de variétés modernes et classiques, qui ne sont pas directement couverts par L'analyse de Turing, par exemple, des algorithmes qui interagissent avec leurs environnements, des algorithmes dont les entrées sont des structures abstraites, et des algorithmes géométriques ou, plus généralement, non discrets »(Blass-Gurevich (2003) p. 8, en gras ajouté)

1954 Caractérisation de AA Markov Jr.

Andrey Markov Jr. (1954) a fourni la définition suivante de l'algorithme:

"1. En mathématiques," algorithme "est généralement compris comme une prescription exacte, définissant un processus de calcul, menant de diverses données initiales au résultat souhaité."
"Les trois caractéristiques suivantes sont caractéristiques des algorithmes et déterminent leur rôle en mathématiques:
«a) la précision de la prescription, ne laissant aucune place à l'arbitraire, et sa compréhensibilité universelle - le caractère définitif de l'algorithme;
"b) la possibilité de commencer avec des données initiales, qui peuvent varier dans des limites données - la généralité de l'algorithme;
"c) l'orientation de l'algorithme vers l'obtention d'un résultat souhaité, qui est effectivement obtenu à la fin avec des données initiales appropriées - le caractère concluant de l'algorithme." (p.1)

Il a admis que cette définition «ne prétend pas à la précision mathématique» (p. 1). Sa monographie de 1954 était sa tentative de définir l'algorithme avec plus de précision; il a vu sa définition résultante - son algorithme «normal» - comme «équivalent au concept de fonction récursive » (p. 3). Sa définition comprenait quatre éléments majeurs (chapitre II, 3 p. 63 et suiv.):

"1. Des étapes élémentaires distinctes, dont chacune sera exécutée selon l'une des règles [de substitution] ... [règles données au départ]
"2. ... étapes de nature locale ... [Ainsi, l'algorithme ne changera pas plus d'un certain nombre de symboles à gauche ou à droite du mot / symbole observé]
"3. Règles pour les formules de substitution ... [il a appelé la liste de ces" le schéma "de l'algorithme]
"4. ... un moyen de distinguer une" substitution finale "[c'est-à-dire un ou plusieurs états" terminaux / finals "distincts]

Dans son introduction, Markov a observé que "toute la signification pour les mathématiques" des efforts visant à définir plus précisément l'algorithme serait "en rapport avec le problème d'une fondation constructive pour les mathématiques" (p. 2). Ian Stewart (cf Encyclopædia Britannica) partage une conviction similaire: "... l'analyse constructive est très proche du même esprit algorithmique que l'informatique ...". Pour en savoir plus, consultez les mathématiques constructives et l' intuitionnisme .

Distinguisabilité et localité : les deux notions sont apparues pour la première fois avec Turing (1936–1937) -

"Les nouveaux carrés observés doivent être immédiatement reconnaissables par l'ordinateur [ sic : un ordinateur était une personne en 1936]. Je pense qu'il est raisonnable de supposer qu'il ne peut s'agir que de carrés dont la distance du plus proche des carrés immédiatement observés ne dépasse pas un un certain montant fixe. Restons que chacun des nouveaux carrés observés est à l'intérieur de L carrés de l'un des carrés précédemment observés. " (Turing (1936) p. 136 dans Davis ed. Indécidable )

La localité apparaît en bonne place dans les travaux de Gurevich et Gandy (1980) (que Gurevich cite). Le «quatrième principe des mécanismes» de Gandy est le «principe de la causalité locale»:

«Nous arrivons maintenant au plus important de nos principes. Dans l'analyse de Turing, l'exigence selon laquelle l'action ne dépend que d'une partie délimitée du document était basée sur une limitation humaine. Nous la remplaçons par une limitation physique que nous appelons le principe du local. causation. Sa justification réside dans la vitesse finie de propagation des effets et des signaux: la physique contemporaine rejette la possibilité d'une action instantanée à distance. " (Gandy (1980) p. 135 dans J. Barwise et al.)

1936, 1963, 1964 Caractérisation de Gödel

1936 : Une citation assez célèbre de Kurt Gödel apparaît dans une "Remarque ajoutée dans la preuve [de la publication originale allemande] dans son article" Sur la longueur des preuves "traduit par Martin Davis paraissant aux pages 82-83 de The Undecidable . A nombre d'auteurs - Kleene, Gurevich, Gandy etc. - ont cité ce qui suit:

«Ainsi, le concept de« calculable »est dans un certain sens défini« absolu », tandis que pratiquement tous les autres concepts métamathématiques familiers (par exemple prouvables, définissables, etc.) dépendent essentiellement du système par rapport auquel ils sont définis. (p. 83)

1963 : Dans une "Note" du 28 août 1963 ajoutée à son célèbre article sur les propositions formellement indécidables (1931), Gödel déclare (dans une note de bas de page) sa conviction que les " systèmes formels " ont "la propriété caractéristique de raisonner en eux, en principe, peut être complètement remplacé par des dispositifs mécaniques »(p. 616 dans van Heijenoort). "... grâce aux" travaux d'AM Turing, une définition précise et incontestablement adéquate de la notion générale de système formel peut maintenant être donnée [et] une version complètement générale des Théorèmes VI et XI est maintenant possible "(p. 616). Dans une note de 1964 à un autre ouvrage, il exprime la même opinion plus fortement et plus en détail.

1964 : Dans un Postscriptum, daté de 1964, à un article présenté à l'Institute for Advanced Study au printemps 1934, Gödel amplifie sa conviction que les «systèmes formels» sont ceux qui peuvent être mécanisés:

"En conséquence des avancées ultérieures, en particulier du fait que, grâce aux travaux d'AM Turing, une définition précise et incontestablement adéquate du concept général de système formel peut maintenant être donnée... Les travaux de Turing donnent une analyse du concept de" procédure mécanique "(alias" algorithme "ou" procédure de calcul "ou" procédure combinatoire finie "). Ce concept est équivalent à celui d'une" machine de Turing ". * Un système formel peut simplement être défini comme une procédure mécanique pour produire des formules, appelées formules prouvables... " (p. 72 dans Martin Davis ed. The Undecidable : "Postscriptum" to "On Undecidable Propositions of Formal Mathematical Systems" apparaissant à la p. 39, loc. cit.)

Le * indique une note de bas de page dans laquelle Gödel cite les articles d' Alan Turing (1937) et d' Emil Post (1936), puis continue en faisant la déclaration intrigante suivante:

"Comme pour les définitions équivalentes précédentes de la calculabilité, qui cependant, sont beaucoup moins adaptées à notre propos, voir Alonzo Church , Am. J. Math., Vol. 58 (1936) [apparaissant dans The Undecidable pp. 100-102]).

Les définitions de Church englobent la soi-disant « récursion » et le « calcul lambda » (c'est-à-dire les fonctions définissables à λ). Sa note de bas de page 18 indique qu'il a discuté de la relation entre «calculabilité effective» et «récursivité» avec Gödel, mais qu'il a indépendamment remis en question «effectivement calculabilité» et «λ-définissabilité»:

«Nous définissons maintenant la notion ... d'une fonction effectivement calculable d'entiers positifs en l'identifiant à la notion de fonction récursive d'entiers positifs 18 (ou d'une fonction λ-définissable d'entiers positifs.
«On a déjà fait remarquer que, pour toute fonction d'entiers positifs effectivement calculable au sens qui vient d'être défini, il existe un algorithme pour le calcul de sa valeur.
"Inversement, c'est vrai ..." (p. 100, L'Indécidable).

Il semblerait d'après ceci, et ce qui suit, qu'en ce qui concerne Gödel, la machine de Turing était suffisante et le calcul lambda était «beaucoup moins approprié». Il poursuit en faisant remarquer qu'en ce qui concerne les limitations de la raison humaine, le jury est toujours absent:

(«Notez que la question de savoir s'il existe des procédures non mécaniques finies ** qui ne sont équivalentes à aucun algorithme, n'a absolument rien à voir avec l'adéquation de la définition de« système formel »et de« procédure mécanique ».) (P. 72, loc. Cit.)
"(Pour les théories et les procédures au sens plus général indiqué dans la note de bas de page **, la situation peut être différente. Notez que les résultats mentionnés dans le post-scriptum n'établissent pas de limites pour les pouvoirs de la raison humaine, mais plutôt pour les potentialités du formalisme pur. en mathématiques.) (p. 73 loc. cit.)
Note de bas de page **: "Ie, comme impliquent l'utilisation de termes abstraits sur la base de leur signification. Voir mon article dans Dial. 12 (1958), p. 280." (cette note de bas de page figure à la p. 72, loc. cit.).

1967 Caractérisation de Minsky

Minsky (1967) affirme catégoriquement qu '«un algorithme est« une procédure efficace »et refuse d'utiliser le mot« algorithme »plus loin dans son texte; en fait, son index montre clairement ce qu'il pense de« l'algorithme, synonyme de procédure efficace »( p. 311):

«Nous utiliserons ce dernier terme [une procédure efficace ] dans la suite. Les termes sont à peu près synonymes, mais il y a un certain nombre de nuances de sens utilisées dans différents contextes, en particulier pour 'algorithme'» (italique dans l'original, p. 105 )

D'autres auteurs (voir Knuth ci-dessous) utilisent le mot «procédure efficace». Cela amène à se demander: quelle est la notion de Minsky de «procédure efficace»? Il commence par:

"... un ensemble de règles qui nous disent, à chaque instant, comment se comporter précisément" (p. 106)

Mais il reconnaît que cela fait l'objet d'une critique:

"... la critique selon laquelle l'interprétation des règles doit dépendre d'une personne ou d'un agent" (p. 106)

Son raffinement? «Préciser, avec l'énoncé des règles, les détails du mécanisme qui doit les interpréter ». Pour éviter le processus "fastidieux" consistant à "devoir recommencer pour chaque procédure individuelle", il espère identifier une " famille raisonnablement uniforme de mécanismes respectant les règles". Sa «formulation»:

"(1) un langage dans lequel des ensembles de règles de comportement doivent être exprimés, et
"(2) une seule machine qui peut interpréter les déclarations dans le langage et ainsi exécuter les étapes de chaque processus spécifié." (italiques dans l'original, tous citent ce paragraphe p. 107)

En fin de compte, cependant, il craint toujours qu '«il reste un aspect subjectif à la question. Différentes personnes peuvent ne pas s'entendre sur la question de savoir si une certaine procédure doit être qualifiée d'effectif» (p. 107)

Mais Minsky n'est pas découragé. Il introduit immédiatement «l'analyse de Turing du processus de calcul» (son chapitre 5.2). Il cite ce qu'il appelle "la thèse de Turing "

«Tout processus qui pourrait naturellement être qualifié de procédure efficace peut être réalisé par une machine de Turing» (p. 108. (Minsky commente que, sous une forme plus générale, cela s'appelle « la thèse de l'Église »).

Après une analyse de "l'argument de Turing" (son chapitre 5.3), il observe que "l'équivalence de nombreuses formulations intuitives" de Turing, Church, Kleene, Post et Smullyan "... nous amène à supposer qu'il y a bien ici un 'objectif 'ou notion' absolue '. Comme l'a dit Rogers [1959]:

«En ce sens, la notion de fonction effectivement calculable est l'un des rares concepts« absolus »produits par les travaux modernes sur les fondements des mathématiques» (Minsky p. 111 citant Rogers, Hartley Jr (1959) La théorie actuelle de la machine de Turing calculabilité , J. SIAM 7, 114-130.)

1967 Caractérisation de Rogers

Dans sa Théorie des fonctions récursives et de la calculabilité effective de 1967, Hartley Rogers caractérise un «algorithme» grosso modo comme «une procédure administrative (c'est-à-dire déterministe, comptable) ... appliquée à ... des entrées symboliques et qui finira par produire, pour chacune de ces entrées. , une sortie symbolique correspondante »(p. 1). Il poursuit ensuite en décrivant la notion «en termes approximatifs et intuitifs» comme ayant 10 «caractéristiques» 5, dont il affirme que «pratiquement tous les mathématiciens seraient d'accord [pour]» (p. 2). Les 5 autres, affirme-t-il, «sont moins évidents que * 1 à * 5 et sur lesquels nous pourrions trouver un accord moins général» (p. 3).

Les 5 "évidents" sont:

  • 1 Un algorithme est un ensemble d'instructions de taille finie,
  • 2 Il existe un agent informatique capable,
  • 3 "Il existe des fonctionnalités pour effectuer, stocker et récupérer les étapes d'un calcul"
  • 4 Étant donné les numéros 1 et 2, l'agent calcule de manière "discrète pas à pas" sans utiliser de méthodes continues ou de dispositifs analogiques ",
  • 5 L'agent informatique fait avancer le calcul "sans recourir à des méthodes ou des dispositifs aléatoires, par exemple, des dés" (dans une note de bas de page, Rogers se demande si les numéros 4 et 5 sont vraiment les mêmes)

Les 5 autres qu'il ouvre au débat sont:

  • 6 Pas de limite fixe sur la taille des entrées,
  • 7 Pas de limite fixe sur la taille du jeu d'instructions,
  • 8 Pas de limite fixe sur la quantité de stockage mémoire disponible,
  • 9 Une limite finie fixe sur la capacité ou la capacité de l'agent de calcul (Rogers illustre par exemple des mécanismes simples similaires à une machine Post-Turing ou une machine de comptage ),
  • 10 Une limite sur la longueur du calcul - "Devrions-nous avoir une idée," à l'avance ", combien de temps le calcul prendra?" (p. 5). Rogers exige «seulement qu'un calcul se termine après un nombre fini d'étapes; nous n'insistons pas sur une capacité a priori d'estimer ce nombre». (p. 5).

1968, 1973 Caractérisation de Knuth

Knuth (1968, 1973) a donné une liste de cinq propriétés qui sont largement acceptées comme conditions requises pour un algorithme:

  1. Finitude : "Un algorithme doit toujours se terminer après un nombre fini d'étapes ... un nombre très fini, un nombre raisonnable"
  2. Définition : "Chaque étape d'un algorithme doit être définie avec précision; les actions à effectuer doivent être spécifiées de manière rigoureuse et sans ambiguïté pour chaque cas"
  3. Entrée : "... quantités qui lui sont données initialement avant le début de l'algorithme. Ces entrées sont prises à partir d'ensembles d'objets spécifiés"
  4. Sortie : "... grandeurs qui ont une relation spécifiée avec les entrées"
  5. Efficacité : "... toutes les opérations à effectuer dans l'algorithme doivent être suffisamment basiques pour qu'elles puissent en principe être effectuées exactement et dans un laps de temps limité par un homme utilisant du papier et un crayon"

Knuth offre comme exemple l' algorithme euclidien pour déterminer le plus grand diviseur commun de deux nombres naturels (cf. Knuth Vol. 1 p. 2).

Knuth admet que, si sa description d'un algorithme peut être intuitivement claire, elle manque de rigueur formelle, car on ne sait pas exactement ce que signifie «défini avec précision», ou «spécifié de manière rigoureuse et sans ambiguïté», ou «suffisamment basique», et donc en avant. Il fait un effort dans ce sens dans son premier volume où il définit en détail ce qu'il appelle le " langage machine " pour son "mythique MIX ... le premier ordinateur polyinsaturé au monde" (pp. 120ff). La plupart des algorithmes de ses livres sont écrits dans le langage MIX. Il utilise également des diagrammes d'arbre , des organigrammes et des diagrammes d'état .

"Bonté" d'un algorithme, "meilleurs" algorithmes : Knuth déclare que "Dans la pratique, nous ne voulons pas seulement des algorithmes, nous voulons de bons algorithmes ...." Il suggère que certains critères de qualité d'un algorithme sont le nombre d'étapes à effectuer l'algorithme, son "adaptabilité aux ordinateurs, sa simplicité et son élégance, etc." Étant donné un certain nombre d'algorithmes pour effectuer le même calcul, lequel est "meilleur"? Il appelle ce type d'enquête «analyse algorithmique: étant donné un algorithme, pour déterminer ses caractéristiques de performance» (tous citent ce paragraphe: Knuth Vol. 1 p. 7)

1972 Caractérisation de Stone

Stone (1972) et Knuth (1968, 1973) étaient professeurs à l'Université de Stanford en même temps, il n'est donc pas surprenant qu'il y ait des similitudes dans leurs définitions (caractères gras ajoutés pour souligner):

"Pour résumer ... nous définissons un algorithme comme un ensemble de règles qui définit précisément une séquence d'opérations telle que chaque règle est efficace et définie et telle que la séquence se termine dans un temps fini." (gras ajouté, p. 8)

Stone est remarquable en raison de sa discussion détaillée de ce qui constitue une règle «efficace» - son robot , ou personne agissant en tant que robot, doit avoir des informations et des capacités en eux, et sinon les informations et la capacité doivent être fournies dans "l'algorithme":

«Pour que les gens suivent les règles d'un algorithme, les règles doivent être formulées de manière à pouvoir être suivies à la manière d'un robot , c'est-à-dire sans avoir besoin de réfléchir ... cependant, si les instructions [pour résoudre le quadratique équation, son exemple] doivent être obéis par quelqu'un qui sait effectuer des opérations arithmétiques mais ne sait pas extraire une racine carrée, alors nous devons également fournir un ensemble de règles pour extraire une racine carrée afin de satisfaire la définition de algorithme "(p. 4-5)

De plus, "... toutes les instructions ne sont pas acceptables , car elles peuvent exiger que le robot ait des capacités au-delà de celles que nous jugeons raisonnables ." Il donne l'exemple d'un robot confronté à la question «Henry VIII un roi d'Angleterre?» et d'imprimer 1 si oui et 0 si non, mais le robot n'a pas reçu auparavant cette information. Et pire, si on demande au robot si Aristote était un roi d'Angleterre et que le robot n'avait reçu que cinq noms, il ne saurait répondre. Ainsi:

«Une définition intuitive d'une séquence d'instructions acceptable est celle dans laquelle chaque instruction est définie avec précision afin que le robot soit assuré de pouvoir y obéir » (p. 6)

Après nous avoir fourni sa définition, Stone introduit le modèle de la machine de Turing et déclare que l'ensemble des cinq tuples qui sont les instructions de la machine est «un algorithme ... connu sous le nom de programme de la machine de Turing» (p. 9). Immédiatement après, il continue à dire qu'un « calcul d'une machine de Turing est décrit en déclarant:

"1. L'alphabet de la bande
"2. La forme sous laquelle les paramètres [d'entrée] sont présentés sur la bande
"3. L'état initial de la machine de Turing
"4. La forme sous laquelle les réponses [sortie] seront représentées sur la bande lorsque la machine de Turing s'arrêtera
"5. Le programme machine" (italiques ajoutés, p. 10)

Cette prescription précise de ce qui est nécessaire pour «un calcul» est dans l'esprit de ce qui va suivre dans les travaux de Blass et Gurevich.

1995 Caractérisation de Soare

"Un calcul est un processus par lequel nous procédons à partir d'objets initialement donnés, appelés entrées , selon un ensemble fixe de règles, appelé programme, procédure ou algorithme , à travers une série d' étapes et arrivons à la fin de ces étapes avec un final entraîner, dite sortie . l' algorithme , comme un ensemble de règles procédant à partir des entrées vers la sortie, doivent être précis et déterminé à chaque étape successive clairement déterminée. la notion de calculabilité concerne les objets qui peuvent être spécifiées en principe par les calculs... "(italiques dans l'original, caractères gras ajoutés p. 3)

2000 Caractérisation de Berlinski

Alors qu'il était étudiant à Princeton au milieu des années 1960, David Berlinski était un étudiant de l'église Alonzo (cf. p. 160). Son livre de l'an 2000 The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer contient la définition suivante de l' algorithme :

" Dans la voix du logicien:
" un algorithme est
une procédure finie,
écrit dans un vocabulaire symbolique fixe,
régi par des instructions précises,
se déplaçant par étapes discrètes, 1, 2, 3,. . .,
dont l'exécution ne nécessite aucune perspicacité, intelligence,
l'intuition, l'intelligence ou la perspicuité,
et cela prend fin tôt ou tard. "(caractères gras et italiques dans l'original, p. xviii)

2000, 2002 Caractérisation de Gurevich

Une lecture attentive de Gurevich 2000 amène à conclure (inférer?) Qu'il croit qu'un "algorithme" est en fait "une machine de Turing" ou "une machine à pointeur " effectuant un calcul. Un «algorithme» n'est pas seulement la table de symboles qui guide le comportement de la machine, ni une seule instance d'une machine effectuant un calcul étant donné un ensemble particulier de paramètres d'entrée, ni une machine convenablement programmée avec la mise hors tension ; au contraire, un algorithme est la machine effectuant réellement tout calcul dont elle est capable . Gurevich ne vient pas tout de suite et le dit, de sorte que, comme indiqué ci-dessus, cette conclusion (inférence?) Est certainement sujette à débat:

"... chaque algorithme peut être simulé par une machine de Turing... un programme peut être simulé et donc donné une signification précise par une machine de Turing." (p. 1)
«On pense souvent que le problème de la formalisation de la notion d'algorithme séquentiel a été résolu par Church [1936] et Turing [1936]. Par exemple, selon Savage [1987], un algorithme est un processus de calcul défini par une machine de Turing. Church et Turing n'ont pas résolu le problème de la formalisation de la notion d'algorithme séquentiel, mais ont donné des formalisations (différentes mais équivalentes) de la notion de fonction calculable, et il y a plus dans un algorithme que la fonction qu'il calcule. 3)
"Bien entendu, les notions d'algorithme et de fonction calculable sont intimement liées: par définition, une fonction calculable est une fonction calculable par un algorithme ... (p. 4)


Dans Blass et Gurevich 2002, les auteurs invoquent un dialogue entre "Quisani" ("Q") et "Authors" (A), utilisant Yiannis Moshovakis comme repoussoir, où ils sortent carrément et déclarent catégoriquement:

" R: Pour localiser le désaccord, mentionnons d'abord deux points d'accord. Premièrement, il y a certaines choses qui sont évidemment des algorithmes selon la définition de n'importe qui - les machines de Turing, les ASM à temps séquentiel [machines à états abstraites], etc. .Deuxièmement, à l'autre extrême, il y a des spécifications qui ne seraient pas considérées comme des algorithmes selon la définition de qui que ce soit, car elles ne donnent aucune indication sur la façon de calculer quoi que ce soit ... Le problème est de savoir dans quelle mesure les informations doivent être détaillées pour être comptées comme un algorithme. [...] Moshovakis autorise certaines choses que nous appellerions seulement des spécifications déclaratives, et il utiliserait probablement le mot «implémentation» pour des choses que nous appelons algorithmes. (paragraphes joints pour faciliter la lecture, 2002: 22)

Cette utilisation du mot «mise en œuvre» va droit au cœur de la question. Au début de l'article, Q déclare sa lecture des Moshovakis:

"... [H] e penserait probablement que votre travail pratique [Gurevich travaille pour Microsoft] vous oblige à penser aux implémentations plus qu'aux algorithmes. Il est tout à fait disposé à identifier les implémentations avec des machines, mais il dit que les algorithmes sont quelque chose de plus Ce que cela revient à dire, c'est que vous dites qu'un algorithme est une machine et Moschovakis dit que ce n'est pas le cas. " (2002: 3)

Mais les auteurs hésitent ici, en disant "[L] et s'en tiennent à" l'algorithme "et à la" machine ", et le lecteur est encore une fois confus. Nous devons attendre Dershowitz et Gurevich 2007 pour obtenir le commentaire suivant:

"... Néanmoins, si l'on accepte le point de vue de Moshovakis, alors c'est" l'implémentation "d'algorithmes que nous avons voulu caractériser." (Cf. Footnote 9 2007: 6)

2003 Caractérisation de Blass et Gurevich

Blass et Gurevich décrivent leur travail comme ayant évolué à partir de la prise en compte des machines de Turing et des machines à pointeur , en particulier des machines Kolmogorov-Uspensky (machines KU), des machines de modification de stockage de Schönhage (SMM) et des automates de liaison tels que définis par Knuth. Les travaux de Gandy et Markov sont également décrits comme des précurseurs influents.

Gurevich propose une définition `` forte '' d'un algorithme (gras ajouté):

"... L'argument informel de Turing en faveur de sa thèse justifie une thèse plus forte: tout algorithme peut être simulé par une machine de Turing ... En pratique, ce serait ridicule ... [Néanmoins,] [c] on généralise Machines de Turing pour que n'importe quel algorithme, peu importe son abstrait, puisse être modélisé par une machine généralisée? ... Mais supposons que de telles machines de Turing généralisées existent. Quels seraient leurs états? ... une structure de premier ordre ... une un petit jeu d'instructions suffit dans tous les cas ... le calcul comme évolution de l'état ... pourrait être non déterministe ... peut interagir avec leur environnement ... [pourrait être] parallèle et multi-agent ... [aurait pu] sémantique dynamique ... [les deux fondements de leur travail sont:] la thèse de Turing ... [et] la notion de structure (du premier ordre) de [Tarski 1933] »(Gurevich 2000, p. 1-2)

Le calcul de la phrase ci-dessus en tant qu'évolution de l'état diffère nettement de la définition de Knuth et Stone - l '«algorithme» en tant que programme de la machine de Turing. Il correspond plutôt à ce que Turing a appelé la configuration complète (cf. la définition de Turing dans Undecidable, p. 118) - et comprend à la fois l'instruction courante (état) et l'état de la bande. [cf Kleene (1952) p. 375 où il montre un exemple de bande avec 6 symboles dessus - tous les autres carrés sont vierges - et comment Gödelize son état combiné table-bande].

Dans les exemples d'algorithmes, nous voyons l' évolution de l'état de première main.

1995 - Daniel Dennett: l'évolution comme processus algorithmique

Le philosophe Daniel Dennett analyse l'importance de l'évolution en tant que processus algorithmique dans son livre de 1995 Darwin's Dangerous Idea . Dennett identifie trois caractéristiques clés d'un algorithme:

  • Neutralité du substrat : un algorithme repose sur sa structure logique . Ainsi, la forme particulière sous laquelle un algorithme se manifeste n'est pas importante (l'exemple de Dennett est une longue division: il fonctionne aussi bien sur papier, sur parchemin, sur écran d'ordinateur, qu'en utilisant des néons ou en skywriting). (p. 51)
  • Insensibilité sous-jacente : quelle que soit la complexité du produit final du processus algorithmique, chaque étape de l'algorithme est suffisamment simple pour être effectuée par un dispositif mécanique non sensible. L'algorithme n'a pas besoin d'un "cerveau" pour le maintenir ou le faire fonctionner. "L'analogie classique des manuels indique que les algorithmes sont des recettes de toutes sortes, conçues pour être suivies par les cuisiniers novices ." (P. 51)
  • Résultats garantis : si l'algorithme est exécuté correctement, il produira toujours les mêmes résultats. "Un algorithme est une recette infaillible." (p. 51)

C'est sur la base de cette analyse que Dennett conclut que "selon Darwin, l'évolution est un processus algorithmique". (p. 60).

Cependant, dans la page précédente, il est sorti sur une branche beaucoup plus éloignée. Dans le contexte de son chapitre intitulé «Les processus en tant qu'algorithmes», il déclare:

"Mais alors ... y a-t-il des limites à ce qui peut être considéré comme un processus algorithmique? Je suppose que la réponse est NON; si vous le vouliez, vous pouvez traiter n'importe quel processus au niveau abstrait comme un processus algorithmique... Si quoi vous semble déroutant est l'uniformité des grains de sable [de l'océan] ou la force de la lame [en acier trempé], une explication algorithmique est ce qui satisfera votre curiosité - et ce sera la vérité.
«Peu importe à quel point les produits d'un algorithme sont impressionnants, le processus sous-jacent ne consiste toujours en rien d'autre qu'un ensemble d' étapes individuelles [ sic ] insensées qui se succèdent sans l'aide d'une supervision intelligente; ils sont 'automatiques' par définition: le fonctionnement de un automate. " (p. 59)

Il n'est pas clair d'après ce qui précède si Dennett déclare que le monde physique par lui-même et sans observateurs est intrinsèquement algorithmique (calcul) ou si un observateur de traitement de symboles est ce qui ajoute du «sens» aux observations.

2002 John Searle ajoute une mise en garde de clarification à la caractérisation de Dennett

Daniel Dennett est un partisan d' une intelligence artificielle forte : l'idée que la structure logique d'un algorithme suffit à expliquer l' esprit . John Searle , le créateur de l' expérience de pensée de la salle chinoise , affirme que «la syntaxe [c'est-à-dire la structure logique] n'est pas en elle-même suffisante pour le contenu sémantique [c'est-à-dire la signification]» ( Searle 2002 , p. 16). En d'autres termes, la «signification» des symboles est relative à l'esprit qui les utilise; un algorithme - une construction logique - en lui-même est insuffisant pour un esprit.

Searle met en garde ceux qui prétendent que les processus algorithmiques (informatiques) sont intrinsèques à la nature (par exemple, les cosmologistes, les physiciens, les chimistes, etc.):

Le calcul est [...] relatif à l'observateur, et c'est parce que le calcul est défini en termes de manipulation de symboles, mais la notion de «symbole» n'est pas une notion de physique ou de chimie. Quelque chose n'est un symbole que s'il est utilisé, traité ou considéré comme un symbole. L'argument de la salle chinoise a montré que la sémantique n'est pas intrinsèque à la syntaxe. Mais ce que cela montre, c'est que la syntaxe n'est pas intrinsèque à la physique. [...] Quelque chose est un symbole uniquement relatif à un observateur, un utilisateur ou un agent qui lui attribue une interprétation symbolique [...] vous pouvez attribuer une interprétation informatique à quoi que ce soit. Mais si la question demande: "La conscience est-elle intrinsèquement computationnelle?" la réponse est: rien n'est intrinsèquement calculatoire [italiques ajoutés pour souligner]. Le calcul n'existe que par rapport à un agent ou un observateur qui impose une interprétation informatique à un phénomène. C'est un point évident. J'aurais dû le voir il y a dix ans, mais je ne l'ai pas fait.

-  John Searle, Searle 2002 , p. 17

2002: Spécification Boolos-Burgess-Jeffrey du calcul de la machine de Turing

Pour des exemples de cette méthode de spécification appliquée à l'algorithme d'addition "m + n", voir Exemples d'algorithmes .

Un exemple de Boolos-Burgess-Jeffrey (2002) (pp. 31–32) démontre la précision requise dans une spécification complète d'un algorithme, dans ce cas pour ajouter deux nombres: m + n. Il est similaire aux exigences Stone ci-dessus.

(i) Ils ont discuté du rôle du "format des nombres" dans le calcul et ont choisi la "notation de pointage" pour représenter les nombres:

"Certes, le calcul peut être plus difficile en pratique avec certaines notations que d'autres ... Mais ... il est en principe possible de le faire dans n'importe quelle autre notation, simplement en traduisant les données ... Aux fins de cadrer une notion de calculabilité rigoureusement définie , il est pratique d'utiliser la notation monadique ou de pointage "(p. 25-26)

(ii) Au début de leur exemple, ils spécifient la machine à utiliser dans le calcul comme une machine de Turing . Ils ont précédemment spécifié (p. 26) que la machine de Turing sera de la variété 4-tuple, plutôt que 5-tuple, variété. Pour plus d'informations sur cette convention, voir Machine de Turing .

(iii) Auparavant, les auteurs ont spécifié que la position de la tête de bande sera indiquée par un indice à droite du symbole scanné. Pour plus d'informations sur cette convention, voir Machine de Turing . (Dans ce qui suit, des caractères gras sont ajoutés pour mettre l'accent):

«Nous n'avons pas donné de définition officielle de ce que signifie une fonction numérique calculable par une machine de Turing , spécifiant comment les entrées ou les arguments doivent être représentés sur la machine, et comment les sorties ou les valeurs sont représentées. Nos spécifications pour un k- Les fonctions de placement des entiers positifs aux entiers positifs sont les suivantes:
"(a) [ Format du nombre initial: ] Les arguments m 1 , ... m k , ... seront représentés en notation monadique [unaire] par des blocs de ces nombres de traits, chaque bloc étant séparé du suivant par un seul vierge, sur une bande autrement vierge.
Exemple: 3 + 2, 111B11
"(b) [ Emplacement initial de la tête, état initial: ] Initialement, la machine balaiera le 1 le plus à gauche sur la bande, et sera dans son état initial, état 1.
Exemple: 3 + 2, 1 1 111B11
"(c) [ Calcul réussi - format de nombre à l'arrêt: ] Si la fonction à calculer attribue une valeur n aux arguments qui sont initialement représentés sur la bande, la machine finira par s'arrêter sur une bande contenant un bloc de traits , et sinon vide ...
Exemple: 3 + 2, 11111
"(d) [ Calcul réussi - emplacement de la tête à l'arrêt: ] Dans ce cas [c] la machine arrêtera de balayer le 1 le plus à gauche sur la bande ...
Exemple: 3 + 2, 1 n 1111
"(e) [ Calcul infructueux - échec de l'arrêt ou de l'arrêt avec un format de nombre non standard: ] Si la fonction à calculer n'attribue aucune valeur aux arguments qui sont initialement représentés sur la bande, la machine ne sera jamais non plus s'arrêtera ou s'arrêtera dans une configuration non standard ... "(ibid)
Exemple: B n 11111 ou B11 n 111 ou B11111 n

Cette spécification est incomplète: elle nécessite l'emplacement où les instructions doivent être placées et leur format dans la machine -

(iv) dans le TABLEAU de la machine à états finis ou, dans le cas d'une machine de Turing universelle sur la bande, et
(v) le tableau d'instructions dans un format spécifié

Ce dernier point est important. Boolos-Burgess-Jeffrey montre (p. 36) que la prévisibilité des entrées dans le tableau permet de "rétrécir" le tableau en mettant les entrées en séquence et en omettant l'état d'entrée et le symbole. En effet, l'exemple de calcul de la machine de Turing ne nécessitait que les 4 colonnes comme indiqué dans le tableau ci-dessous (mais attention: celles-ci étaient présentées à la machine en lignes ):

État qk
Symbole scanné
action
État suivant qk
État qn
Symbole scanné
action
État suivant qk
État qk
Action B
B-état suivant qkB
1 action
1: état suivant qk1
1 B R H 1 1 R 2 1 R H R 2
2 B P 3 2 1 R 2 2 P 3 R 2
3 B L 4 3 1 R 3 3 L 4 R 3
4 B L 5 4 1 E 4 4 L 5 E 4
5 B R H 5 1 L 5 5 R H L 5

2006: l'affirmation de Sipser et ses trois niveaux de description

Pour des exemples de cette méthode de spécification appliquée à l'algorithme d'addition "m + n", voir Exemples d'algorithmes .

Sipser commence par définir «l'algorithme» comme suit:

"De manière informelle, un algorithme est un ensemble d'instructions simples pour effectuer une tâche. Communs dans la vie de tous les jours, les algorithmes sont parfois appelés procédures ou recettes (en italique dans l'original, p. 154)
"... notre véritable objectif à partir de maintenant est sur les algorithmes. Autrement dit, la machine de Turing sert simplement de modèle précis pour la définition de l'algorithme ... nous devons seulement être suffisamment à l'aise avec les machines de Turing pour croire qu'elles capturent tous les algorithmes "(p. 156)

Sipser signifie-t-il que «algorithme» n'est que des «instructions» pour une machine de Turing, ou est-ce que la combinaison «d'instructions + une (variété spécifique de) machine de Turing»? Par exemple, il définit les deux variantes standard (multi-bande et non déterministe) de sa variante particulière (pas la même que l'original de Turing) et continue, dans ses Problèmes (pages 160-161), à décrire quatre autres variantes ( écriture une fois, bande doublement infinie (c.-à-d. gauche et droite infinie), réinitialisation à gauche, et "rester en place au lieu de gauche). De plus, il impose certaines contraintes. Premièrement, l'entrée doit être encodée sous forme de chaîne (p. 157) et dit des encodages numériques dans le contexte de la théorie de la complexité:

"Mais notez que la notation unaire pour le codage des nombres (comme dans le nombre 17 codé par le nombre unaire 11111111111111111) n'est pas raisonnable car elle est exponentiellement plus grande que les codages vraiment raisonnables, comme la notation de base k pour tout k ≥ 2." (p. 259)

Van Emde Boas commente un problème similaire en ce qui concerne le modèle abstrait de calcul de la machine à accès aléatoire (RAM) parfois utilisé à la place de la machine de Turing lors d'une "analyse d'algorithmes": "L'absence ou la présence de manipulation multiplicative et parallèle des bits les opérations sont importantes pour la compréhension correcte de certains résultats dans l'analyse des algorithmes.

"... [T] n'existe guère ici comme une extension" innocente "du modèle de RAM standard dans les mesures de temps uniformes; soit on n'a qu'une arithmétique additive, soit on pourrait tout aussi bien inclure tous les multiplicatifs raisonnables et / ou au niveau du bit. Instructions booléennes sur les petits opérandes. " (Van Emde Boas, 1990: 26)

En ce qui concerne un "langage de description" pour les algorithmes, Sipser termine le travail que Stone et Boolos-Burgess-Jeffrey ont commencé (gras ajouté). Il nous propose trois niveaux de description des algorithmes de la machine de Turing (p. 157):

Description de haut niveau : "où nous utilisons ... de la prose pour décrire un algorithme, en ignorant les détails d'implémentation. A ce niveau, nous n'avons pas besoin de mentionner comment la machine gère sa bande ou sa tête."
Description de l'implémentation : "dans laquelle nous utilisons ... de la prose pour décrire la façon dont la machine de Turing bouge sa tête et la façon dont elle stocke les données sur sa bande. A ce niveau, nous ne détaillons pas les états ou la fonction de transition."
Description formelle : "... le niveau de description le plus bas, le plus détaillé ... qui décrit en détail les états de la machine de Turing, la fonction de transition, etc."

Remarques

Les références

  • David Berlinski (2000), L'avènement de l'algorithme: le voyage de 300 ans d'une idée à l'ordinateur , Harcourt, Inc., San Diego, ISBN   0-15-601391-6 (pbk.)
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Quatrième édition , Cambridge University Press, Cambridge, Royaume-Uni. ISBN   0-521-00758-5 (pbk).
  • Andreas Blass et Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions , Bulletin de l'Association européenne pour l'informatique théorique 81, 2003. Comprend une excellente bibliographie de 56 références.
  • Burgin, M. Algorithmes super-récursifs , Monographies en informatique, Springer, 2005. ISBN   0-387-95569-0
  • Davis, Martin (1958). Calculabilité et insolvabilité . New York: McGraw-Hill Book Company, Inc. . Une source de définitions importantes et de quelques algorithmes basés sur la machine de Turing pour quelques fonctions récursives.
  • Davis, Martin (1965). L'indécidable: documents de base sur les propositions indécidables, les problèmes insolubles et les fonctions calculables . New York: Raven Press. Davis donne des commentaires avant chaque article. Les articles de Gödel , Alonzo Church , Turing , Rosser , Kleene et Emil Post sont inclus.
  • Dennett, Daniel (1995). Idée dangereuse de Darwin . New York: Touchstone / Simon & Schuster.
  • Robin Gandy , Thèse et principes de l'Église pour les mécanismes , dans J. Barwise , HJ Keisler et K. Kunen , éds., The Kleene Symposium , North-Holland Publishing Company 1980) pp. 123-148. Les fameux «4 principes des mécanismes [de calcul]» de Gandy comprennent le «Principe IV - Le principe de causalité locale».
  • Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (juillet 2000), pages 77-111. Comprend une bibliographie de 33 sources.
  • Kleene C., Stephen (1943). "Prédicats et quantificateurs récursifs" . Transactions de la Société mathématique américaine . Transactions de l'American Mathematical Society, Vol. 53, n ° 1. 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR   1990131 . Réimprimé dans The Undecidable , p. 255ff. Kleene a affiné sa définition de la «récursion générale» et a procédé dans son chapitre «12. Théories algorithmiques» pour poser «Thèse I» (p. 274); il répéterait plus tard cette thèse (dans Kleene 1952: 300) et la nommerait «Thèse de l'Église» (Kleene 1952: 317) (c'est-à-dire la Thèse de l' Église ).
  • Kleene, Stephen C. (1991) [1952]. Introduction aux métamathématiques (dixième éd.). Société d'édition de Hollande du Nord. Excellente - source de référence accessible et lisible pour les «fondements» mathématiques.
  • Knuth, Donald E. (1973) [1968]. L'art de la programmation informatique, deuxième édition, volume 1 / algorithmes fondamentaux (2e éd.). Société d'édition Addison-Wesley. Le premier de la célèbre série de trois textes de Knuth.
  • Lewis, HR et Papadimitriou, CH Elements of the Theory of Computation , Prentice-Hall, Uppre Saddle River, NJ, 1998
  • AA Markov (1954) Théorie des algorithmes . [Traduit par Jacques J. Schorr-Kon et le personnel du PST] Mentions légales Moscou, Académie des sciences de l'URSS, 1954 [c.-à-d. Jérusalem, Programme israélien de traductions scientifiques, 1961; disponible auprès du Bureau des services techniques, Département américain du commerce, Washington] Description 444 p. 28 cm. Ajout de tp dans Traduction russe des œuvres de l'Institut mathématique, Académie des sciences de l'URSS, v. 42. Titre original: Teoriya algerifmov. [QA248.M2943 Bibliothèque du Dartmouth College. Département du commerce des États-Unis, Bureau des services techniques, numéro OTS 60-51085.]
  • Minsky, Marvin (1967). Calcul: Machines finies et infinies (première éd.). Prentice-Hall, Englewood Cliffs, NJ. Minsky développe son "... idée d'un algorithme - une procédure efficace ..." dans le chapitre 5.1 Calculabilité, procédures efficaces et algorithmes. Machines infinies.
  • Hartley Rogers, Jr , (1967), Theory of Recursive Functions and Effective Computability , MIT Press (1987), Cambridge MA, ISBN   0-262-68052-1 (pbk.)
  • Searle, John (2002). Conscience et langage . Cambridge Royaume-Uni: Cambridge University Press. ISBN   0-521-59744-7 .
  • Robert Soare , (1995 à paraître dans les Actes du 10e Congrès international de logique, méthodologie et philosophie des sciences , 19-25 août 1995, Florence Italie), Computability and Recursion ), sur le Web à ??.
  • Michael Sipser , (2006), Introduction à la théorie du calcul: deuxième édition , Thompson Course Technology div. de Thompson Learning, Inc. Boston, MA. ISBN   978-0-534-95097-2 .
  • Ian Stewart , algorithme , Encyclopædia Britannica 2006.
  • Stone, Harold S. Introduction à l'organisation informatique et aux structures de données (1972 éd.). McGraw-Hill, New York. Cf en particulier le premier chapitre intitulé: Algorithmes, Machines de Turing et Programmes . Sa définition informelle succincte: "... toute séquence d'instructions à laquelle un robot peut obéir, s'appelle un algorithme " (p. 4).
  • Peter van Emde Boas (1990), "Machine Models and Simulations" pp 3–66, apparaissant dans Jan van Leeuwen (1990), Handbook of Theoretical Computer Science. Volume A: Algorithmes et complexité , The MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (Volume A)