JavaScript est Turing terminé - expliqué

JavaScript est Turing terminé - expliqué

Si vous commencez à apprendre la programmation fonctionnelle en JavaScript, vous entendrez probablement parler de lambda calcul, de la machine de Turing, de Turing complet et en quelque sorte de «JavaScript est Turing complet».

Mais personne ne semble expliquer, en termes simples, ce que cela signifie réellement. Quelle est la relation b / wa Turing «machine» et «langage» JavaScript? En outre, la plupart des gens utilisent le jargon pour expliquer le jargon comme suit:

Dans la théorie de la calculabilité, un système de règles de manipulation de données (tel que le jeu d'instructions d'un ordinateur, un langage de programmation ou un automate cellulaire) est considéré comme Turing complet ou universel par le calcul s'il peut être utilisé pour simuler n'importe quelle machine de Turing à enregistrement unique. . Le concept est nommé d'après le mathématicien anglais Alan Turing. Un exemple classique est le calcul lambda.

C'est donc ma tentative d'expliquer simplement ces concepts.

Machines de Turing

À l'époque, les gens voulaient savoir comment créer une machine capable de faire tous les calculs qu'ils faisaient à la main. Ils voulaient savoir comment construire une telle machine et comment cela pourrait fonctionner.

Alan Turing a proposé une machine hypothétique qui pourrait prendre n'importe quel programme de n'importe quelle complexité et l'exécuter. Il pourrait être mis en œuvre à l'aide d'une simple bande, une tête qui se déplace à gauche et à droite, pourrait stocker des données en lisant, en écrivant et en effaçant le contenu des cellules carrées. Avec une bande suffisamment longue et suffisamment de temps, il pourrait calculer n'importe quel programme.

En d'autres termes, il a expliqué comment quelqu'un peut construire un ordinateur. Et a appelé l'ordinateur une «machine de Turing»

Trivia: À l'époque d'Alan Turing, le mot «ordinateur» désignait la personne qui calcule manuellement les programmes (pas les machines) :)

Si puissant mais si simple

Les machines de Turing sont rapidement devenues très populaires, et finalement une norme car, bien qu'elles fournissaient un mécanisme puissant pour calculer quoi que ce soit, elles étaient également faciles à comprendre. Comme décrit dans la vidéo ci-dessous, les machines de Turing utilisent une bande pour garder une trace des états et exécuter des calculs.

Machines de rubanage à ruban «simple» ou «multi»

Un autre jargon que vous entendrez à propos des machines de Turing est le concept de bande «unique».

La version initiale de la machine de Turing ne comportait qu'une seule bande longue. Plus tard, les gens ont proposé le concept de machines de Turing «multiples» à bande qui utilisaient de deux à cinq bandes. Les machines de Turing à bandes multiples n'étaient pas plus puissantes que les machines à bande unique, mais elles contribuaient à simplifier les programmes.

Il n'est donc pas nécessaire de dire explicitement «bande unique».

Turing terminé

Si une machine physique (comme un ordinateur) ou une machine virtuelle, qui est un logiciel, (comme JavaVM) peut prendre n'importe quel programme et l'exécuter comme une machine de Turing, alors cette machine est appelée «Turing Complete». PS: C'est une sorte de certification.

Exemples: Turing complète Vs Turing machine incomplète

Une calculatrice est un bon exemple de machine incomplète de Turing car elle ne peut effectuer qu'un petit sous-ensemble prédéfini de calculs.

Cependant, un ordinateur domestique (Mac ou PC) est une machine complète de Turing car elle peut faire n'importe quel calcul qu'une machine de Turing peut faire si nous lui donnons suffisamment de mémoire et de temps.

"JavaScript est terminé"

Si vous y réfléchissez bien, une machine de Turing n'est qu'un concept - cela signifie que toute « chose » (physique ou virtuelle) qui prend n'importe quel programme et l'exécute est essentiellement une machine de Turing. Et si cette «chose» peut exécuter tous les programmes qu'une «machine de Turing» peut exécuter, alors elle s'appelle «Turing Complete».

Maintenant, si vous pensez à un langage de programmation moderne, ils prennent également des programmes (écrits par nous) en entrée et les exécutent. De plus, tout programme qui peut être théoriquement écrit pour s'exécuter sur une machine de Turing peut également être écrit en JavaScript. Ainsi, JavaScript est Turing complet.

C'est ça!

??? Si vous aimez ce message, veuillez 1. ❤❤❤ le ci- dessous sur Medium et 2. partagez-le sur Twitter. Vous pouvez retweeter la carte ci-dessous ???

Mes autres messages

DERNIER: Programmation fonctionnelle dans JS - avec des exemples pratiques (partie 1)

Programmation fonctionnelle

  1. JavaScript est Turing complet - expliqué
  2. Programmation fonctionnelle dans JS - avec des exemples pratiques (partie 1)

ES6

  1. 5 pièces JavaScript «mauvaises» corrigées dans ES6
  2. La «classe» dans ES6 est-elle la nouvelle «mauvaise» partie?

WebPack

  1. Webpack - Les éléments déroutants
  2. Remplacement du Webpack et du module à chaud [HMR] (sous le capot)
  3. HMR et React-Hot-Loader de Webpack - Le manuel manquant

Draft.js

  1. Pourquoi Draft.js et pourquoi vous devriez contribuer
  2. Comment Draft.js représente les données de texte enrichi

Réagissez et Redux:

  1. Guide étape par étape pour créer des applications React Redux
  2. Un guide pour créer une application React Redux CRUD ( application de 3 pages)
  3. Utilisation des middlewares dans les applications React Redux
  4. Ajout d'une validation de formulaire robuste pour réagir aux applications Redux
  5. Sécuriser les applications React Redux avec des jetons JWT
  6. Gestion des e-mails transactionnels dans les applications React Redux
  7. L'anatomie d'une application React Redux

Salesforce

  1. Développement d'applications React Redux dans Visualforce de Salesforce

Merci d'avoir lu!