JavaScript е Тюринг завършен - Обяснено

JavaScript е Тюринг завършен - Обяснено

Ако започнете да изучавате функционално програмиране в JavaScript, вероятно ще чуете за ламбда смятане, машина на Тюринг, Тюринг завършен и по някакъв начин „JavaScript е Тюринг завършен“.

Но, изглежда, никой не обяснява с прости думи какво всъщност означава. Каква е връзката между b / wa Тюринг „машина“ и JavaScript „език“? Също така, повечето хора използват жаргон, за да обяснят жаргона така:

В теорията на изчислимостта се казва, че система от правила за манипулиране на данни (като набор от инструкции на компютъра, език за програмиране или клетъчен автомат) е цялостна или изчислително универсална на Тюринг, ако може да се използва за симулиране на всяка лента с машина . Концепцията е кръстена на английския математик Алън Тюринг. Класически пример е ламбда смятането.

Така че това е моят опит да обясня тези изводи просто.

Машини на Тюринг

Навремето хората искаха да знаят как да създадат машина, която да може да прави всички изчисления, които правеха на ръка. Те искаха да знаят как да създадат такава машина и как тя може да работи.

Алън Тюринг излезе с хипотетична машина, която може да вземе всяка програма с всякаква сложност и да я стартира. Той може да бъде реализиран с помощта на обикновена лента, глава, която се движи наляво и надясно, може да съхранява данни чрез четене, писане и изтриване на съдържанието на квадратни клетки. Като се има предвид достатъчно дълга лента и достатъчно време, тя може да изчисли всяка програма.

С други думи, той обясни как някой може да изгради компютър. И нарече компютъра „машина на Тюринг“

Любопитни факти: Още по времето на Алън Тюринг думата „Компютър“ означаваше човека, който ръчно изчислява програми (не машините) :)

Толкова мощен, но толкова прост

Машините на Тюринг скоро станаха много популярни и в крайна сметка стандарт, тъй като, въпреки че осигуряваха мощен механизъм за изчисляване на каквото и да било, те също бяха лесни за разбиране. Както е описано във видеото по-долу, машините на Тюринг използват лента, за да следят състоянията и да изпълняват изчисления.

„Единични“ срещу „Мулти“ лентоуплътнителни машини

Друг жаргон, който ще чуете за машините на Тюринг, е концепцията за „единична“ лента.

Първоначалната версия на машината на Тюринг имаше само дълга единична лента. По-късно хората излязоха с концепцията за „множество“ лентови машини на Тюринг, които използваха две до пет ленти. Многолентовите машини на Тюринг не бяха по-мощни от еднолентовите, но спомогнаха за опростяване на програмите.

Така че изрично да се казва „единична“ лента не е необходимо.

Тюринг пълен

Ако физическа машина (като компютър) или виртуална машина, която е софтуер (като JavaVM) може да вземе всяка програма и да я стартира точно като машина на Тюринг, тогава тази машина се нарича „Turing Complete“. PS: Това е вид сертификация.

Примери: Тюринг пълен Vs Turing непълна машина

Калкулаторът е добър пример за непълна машина на Тюринг, тъй като може да извършва само малка предварително дефинирана подгрупа от изчисления.

Въпреки това домашният компютър (Mac или PC) е цялостна машина на Turing, защото може да направи всяко изчисление, което може да направи машина на Turing, ако му предоставим достатъчно памет и време.

„JavaScript е Тюринг завършен“

Ако се замислите, машина на Тюринг е просто концепция - това означава, че всяко „ нещо “ (физическо или виртуално), което взема всяка програма и я стартира, е по същество машина на Тюринг. И ако това „нещо“ може да стартира всяка програма, която може да изпълнява „машина на Тюринг“, то тя се нарича „Тюринг завършена“.

Сега, ако мислите за някой съвременен език за програмиране, те също вземат програми (написани от нас) като вход и ги изпълняват. Освен това всяка програма, която може да бъде написана теоретично, за да работи за машина на Тюринг, може да бъде написана и в JavaScript. По този начин JavaScript е завършен на Тюринг.

Това е!

??? Ако харесвате тази публикация, моля, 1. ❤❤❤ я по-долу в Medium и 2. моля, споделете я в Twitter. Можете да ретвирате картата по-долу ???

Другите ми публикации

ПОСЛЕДНО: Функционално програмиране в JS - с практически примери (част 1)

Функционално програмиране

  1. JavaScript е Тюринг завършен - обяснен
  2. Функционално програмиране в JS - с практически примери (част 1)

ES6

  1. 5 „лоши“ части на JavaScript, които са фиксирани в ES6
  2. „Клас“ в ES6 ли е новата „лоша“ част?

WebPack

  1. Webpack - объркващите части
  2. Замяна на уеб пакет и горещ модул [HMR] (под капака)
  3. HMR и React-Hot-Loader на Webpack - липсващото ръководство

Draft.js

  1. Защо Draft.js и защо трябва да допринесете
  2. Как Draft.js представлява богати текстови данни

React и Redux:

  1. Ръководство стъпка по стъпка за изграждане на React Redux Apps
  2. Ръководство за изграждане на React Redux CRUD App ( приложение от 3 страници)
  3. Използване на Middlewares в React Redux Apps
  4. Добавяне на надеждна проверка на формуляра за реакция на Redux Apps
  5. Защита на React Redux Apps с JWT Tokens
  6. Обработка на транзакционни имейли в React Redux Apps
  7. Приложението Anatomy Of A React Redux

Salesforce

  1. Разработване на React Redux Apps в Visualforce на Salesforce

Благодаря за четенето!