Calcul

Un calcul est tout type de calcul arithmétique ou non arithmétique bien défini. Les exemples courants de calcul sont la résolution d'équations mathématiques et l' exécution d' algorithmes informatiques .

Les dispositifs mécaniques ou électroniques (ou, historiquement , les personnes) qui effectuent des calculs sont appelés ordinateurs . L'informatique est un domaine académique qui étudie le calcul.

L'idée que les énoncés mathématiques doivent être « bien définis » a été débattue par les mathématiciens depuis au moins le XVIIe siècle , mais un consensus sur une définition adéquate s'est avéré difficile à atteindre . Plusieurs mathématiciens ont proposé indépendamment une définition candidate dans les années 1930 . La variante la plus connue a été formalisée par le mathématicien Alan Turing , qui a défini un énoncé ou un calcul bien défini comme tout énoncé pouvant être exprimé à l'aide des paramètres d'initialisation d'une machine de Turing . Parmi les autres définitions (mathématiquement équivalentes), on peut citer la lambda-définissabilité d' Alonzo Church , la récursivité générale de Herbrand - Gödel - Kleene et la 1-définissabilité d' Emil Post .

Aujourd’hui, tout énoncé ou calcul formel qui présente cette qualité de définition précise est qualifié de calculable , tandis que l’énoncé ou le calcul lui-même est appelé calcul .

La définition de Turing attribuait la « bonne définition » à une très large classe d'énoncés mathématiques, y compris tous les énoncés algébriques bien formés et tous les énoncés écrits dans les langages de programmation informatique modernes.

Malgré l'adoption généralisée de cette définition, certains concepts mathématiques ne sont pas bien caractérisés selon cette définition. C'est le cas notamment du problème de l'arrêt et du jeu du castor affairé . La question de savoir s'il existe une définition plus puissante de « bien défini » qui puisse englober à la fois les énoncés calculables et non calculables reste ouverte.

Voici quelques exemples d'énoncés mathématiques calculables :

• Toutes les instructions caractérisées dans les langages de programmation modernes, y compris C++ , Python et Java
• Tous les calculs effectués par un ordinateur électronique , une calculatrice ou un boulier
• Tous les calculs ont été effectués sur un moteur analytique.
• Tous les calculs ont été effectués sur une machine de Turing.
• La majorité des énoncés et calculs mathématiques présentés dans les manuels de mathématiques

Voici quelques exemples d'énoncés mathématiques non calculables :

• Calculs ou énoncés mal définis, de sorte qu'ils ne peuvent pas être encodés sans ambiguïté dans une machine de Turing : (« Paul m'aime deux fois plus que Joe »).
• Des énoncés de problèmes qui semblent bien définis, mais pour lesquels il est possible de prouver qu'il n'existe aucune machine de Turing pour les résoudre (comme le problème de l'arrêt ).

Le calcul peut être perçu comme un processus purement physique se déroulant au sein d'un système physique clos appelé ordinateur . La démonstration de Turing en 1937, intitulée « Sur les nombres calculables, avec une application au problème de la décision » , a établi une équivalence formelle entre les énoncés calculables et certains systèmes physiques, communément appelés ordinateurs . Parmi ces systèmes physiques, on peut citer : les machines de Turing , les mathématiciens suivant des règles strictes, les ordinateurs numériques , les ordinateurs mécaniques , les ordinateurs analogiques , etc.

Une autre conception du calcul se retrouve dans les travaux d' Hilary Putnam et d'autres chercheurs. Peter Godfrey-Smith l'a nommée « conception par correspondance simple » . Gualtiero Piccinini résume cette conception en affirmant qu'un système physique effectue un calcul spécifique lorsqu'il existe une correspondance entre l'état de ce système et le calcul, de sorte que les « états microphysiques [du système] reflètent les transitions d'état entre les états de calcul »

Des philosophes comme Jerry Fodor ont proposé diverses conceptions du calcul, en imposant que le contenu sémantique soit une condition nécessaire à son fonctionnement (autrement dit, ce qui distingue un système physique quelconque d'un système informatique, c'est que les opérandes du calcul représentent quelque chose). Cette notion vise à éviter l'abstraction logique de la conception pancomputationaliste , selon laquelle tout peut être considéré comme calculant tout.

Gualtiero Piccinini propose une conception du calcul fondée sur la philosophie mécanique . Selon lui, les systèmes de calcul physique sont des mécanismes qui, par conception, effectuent un calcul physique, c'est-à-dire la manipulation (par un mécanisme fonctionnel) d'un véhicule « indépendant du support » selon une règle. L'« indépendance du support » requiert que cette propriété puisse être instanciée par de multiples réalisateurs et mécanismes, et que les entrées et sorties du mécanisme soient également réalisables de multiples manières . En bref, l'indépendance du support permet l'utilisation de variables physiques dont les propriétés sont autres que la tension (comme dans les ordinateurs numériques classiques) ; ceci est essentiel pour considérer d'autres types de calcul, tels que ceux qui se produisent dans le cerveau ou dans un ordinateur quantique . Une règle, en ce sens, établit une correspondance entre les entrées, les sorties et les états internes du système de calcul physique.

En théorie du calcul , divers modèles mathématiques de calcul ont été développés. Voici quelques exemples typiques de modèles mathématiques d'ordinateurs :

• Modèles d'états incluant la machine de Turing , l'automate à pile , l'automate à états finis et la PRAM
• Modèles fonctionnels, y compris le lambda-calcul
• Modèles logiques, y compris la programmation logique
• Modèles concurrents incluant le modèle d'acteur et les calculs de processus

Giunti nomme « systèmes de calcul » les modèles étudiés par la théorie du calcul, et il soutient qu'il s'agit de systèmes dynamiques mathématiques à temps et espace d'états discrets. Il affirme qu'un système de calcul est un objet complexe composé de trois parties : premièrement, un système dynamique mathématique à temps et espace d'états discrets ; deuxièmement, une configuration de calcul , constituée d'une partie théorique et d'une partie réelle ; troisièmement, une interprétation , qui relie le système dynamique à la configuration .