L'élève d'Alan Turing, Robin Gandy, a-t-il affirmé que Charles Babbage n'avait aucune notion d'une machine informatique universelle?

10

Robin Gandy était un étudiant d' Alan Turing .

Gandy a fait une analyse du moteur analytique de Babbage (voir 'Gandy - The Confluence of Ideas in 1936' cité dans 'Herken, Rolf - The Universal Turing Machine - A Half-Century Survey . Springer Verlag') - et l'a dit (cf. p. 52-53):

  1. Les fonctions arithmétiques +, -, ×, où - indique une soustraction "correcte" x - y = 0 si y ≥ x.
  2. Toute séquence d'opérations est une opération.
  3. Itération d'une opération (répétition de n fois une opération P).
  4. Itération conditionnelle (répétition de n fois une opération P conditionnelle au "succès" du test T).
  5. Transfert conditionnel (c.-à-d. «Goto» conditionnel).

Puis il déclare

les fonctions qui peuvent être calculées par (1), (2) et (4) sont précisément celles qui sont calculables par Turing.

(p. 53).

Puis il déclare:

… L'accent est mis sur la programmation d'une séquence itérable fixe d'opérations arithmétiques. L'importance fondamentale de l'itération conditionnelle et du transfert conditionnel pour une théorie générale des machines à calculer n'est pas reconnue…

Gandy p. 55

J'évalue la portée de la revendication de Gandy ici. (Que ce soit bien ou mal). Il semble affirmer que bien que Babbage semble être tombé sur une notion de complétude de Turing (peut exprimer n'importe quel programme en utilisant (1), (2) et (4) - il n'avait pas la notion d'une fonction calculable . (Peut-être Gandy disait que puisque le travail de Babbage était antérieur au travail de Hilbert et Godel , il n'avait pas les outils mathématiques pour fixer la définition d'une machine informatique universelle.)

Ma question est la suivante: l'élève d'Alan Turing, Robin Gandy, a-t-il affirmé que Charles Babbage n'avait aucune idée d'une machine informatique universelle?

oeil de faucon
la source
2
Notez qu'il y a aussi une histoire de la science et des mathématiques stackexchange hsm.stackexchange.com
usul
Je suis un peu confus par le référencement de la page. Si tous les numéros de page sont ceux de Gandy, il serait peut-être plus clair de dire "(Gandy, p. 52-53)", (Gandy, p. 53) "et (Gandy, p. 55)". Pour tous les extraits cités dans Rolf, l'attribution pourrait être étendue de la manière suivante: (Gandy, p. 5x; tel que cité dans Rolf, p. Xx) ". " Cf. " est l'abréviation de Latin confer / conferatur (" compare "), ce qui signifie "allez voir aussi cette autre chose pour la comparaison ou le contraste", donc cela n'a pas de sens de dire que pour la chose principale que vous citez.
Jacob C. dit Reinstate Monica

Réponses:

22

Non, c'est le contraire. Cette citation de Gandy ne fait pas référence à Babbage, mais à certaines propositions intermédiaires pour un calcul de style universel entre Babbage et Turing. Gandy dit que ces propositions n'avaient pas la reconnaissance de Babbage de l'importance de la ramification et de l'itération pour le calcul universel.


Dans "The Confluence of Ideas in 1936" de Gandy, tel qu'imprimé dans le livre "The Universal Turing Machine - A Half Half Survey", la section 2 est "Babbage and His Followers".

Ici, Gandy souligne que Babbage a bien compris et respecté "l'itération conditionnelle" et le "transfert conditionnel", par exemple fin de p53 et haut de p54

Bien que Babbage mentionne le transfert conditionnel (67-68), lui, avec un respect naturel pour une programmation bien structurée, n'utilise que l'itération conditionnelle [....] Il déclare explicitement le transfert conditionnel (240), permettant qu'une instruction «aller à» il peut être nécessaire d'exécuter en faisant sonner une cloche pour convoquer le préposé; il donne un exemple de son utilisation (241).

(Ici, Gandy se réfère à l'article de Menabrea 1842 sur le moteur de Babbage, mais semble attribuer les idées à Babbage lui-même.)

Gandy cite ensuite Babbage

Que l'ensemble du développement et des opérations d'analyse peuvent désormais être exécutés par des machines.

et écrit

Babbage, dans son travail sur l'algèbre générale et les équations fonctionnelles, avait montré sa capacité à penser en termes abstraits. Si, alors, on l'avait amené à spéculer (pas difficile!) Sur ce qui pouvait être fait avec une machine abstraite, libre de toute limitation de son stockage, il aurait sûrement sanctionné une version (basée sur les sections 2.1. (1) - (5)) de la thèse de Church.

Gandy passe ensuite à la section 2.3, «Développements ultérieurs». Il écrit

D'autres auteurs, préoccupés par des machines plus pratiques, ont fait référence au travail de Babbage. Des exemples de Randell 1982 sont: M. d'Ocagne [1922], L. Couffignal [1933], V. Bush 1936, HH Aiken 11964] (qui est un mémorandum non publié de 1937). Mais l'accent est mis sur la programmation d'une séquence itérable fixe d'opérations arithmétiques. L'importance fondamentale de l'itération conditionnelle et du transfert conditionnel pour une théorie générale des machines à calculer n'est pas reconnue, bien que les principes puissent être utilisés dans des contextes très particuliers [....]

Enfin, Gandy écrit:

Conclusions. Babbage a affirmé ce qui était, en fait, une version de la thèse de Church. Son travail n'a jamais été entièrement oublié, mais son importance théorique - son importance, pour ainsi dire, en tant que logiciel - était peu reconnue [....]

usul
la source