ЈаваСцрипт је Туринг комплетан - објашњен

ЈаваСцрипт је Туринг комплетан - објашњен

Ако почнете да учите функционално програмирање на ЈаваСцрипт-у, вероватно ћете чути за ламбда рачун, Турингову машину, Туринг-ов потпун и некако „ЈаваСцрипт је Туринг-ов потпун“.

Али, изгледа да нико једноставним речима не објашњава шта то заправо значи. Какав је однос б / ва Турингове „машине“ и ЈаваСцрипт „језика“? Такође, већина људи користи жаргон да би објаснила жаргон тако:

У теорији израчунавости, за систем правила за манипулацију подацима (попут рачунарског скупа инструкција, програмског језика или ћелијског аутомата) каже се да је Тјурингов потпун или рачунски универзалан ако се може користити за симулацију било које Турингове машине са једним траком . Концепт је добио име по енглеском математичару Алану Турингу. Класичан пример је ламбда рачун.

Дакле, ово је мој покушај да објасним ове концепте једноставно.

Турингове машине

Некада су људи желели да знају како да направе машину која може ручно да врши све прорачуне које су радили. Желели су да знају како да направе такву машину и како би могла да функционише.

Алан Туринг је смислио хипотетичку машину која може да преузме било који програм било које сложености и покрене га. Могло би се применити помоћу једноставне траке, главе која се помера лево и десно, могао би чувати податке читањем, писањем и брисањем садржаја квадратних ћелија. С обзиром на довољно дугу траку и довољно времена, могао би израчунати било који програм.

Другим речима, објаснио је како неко може да направи рачунар. И назвао рачунар „Тјуринговом машином“

Тривиа: Још у време Алана Туринга реч „рачунар“ значила је особу која ручно рачуна програме (а не машине) :)

Тако моћан, а тако једноставан

Тјурингове машине убрзо су постале веома популарне, а на крају и стандард, јер иако су пружале моћан механизам за израчунавање било чега, оне су такође биле лако разумљиве. Као што је описано у видео снимку испод, Тјурингове машине користе траку да прате стања и покрећу прорачуне.

„Једноструке“ и „вишеструке“ машине за лепљење траке

Још један жаргон који ћете чути о Туринговим машинама је концепт „једне“ траке.

Почетна верзија Тјурингове машине имала је само дугачку једну траку. Касније су људи смислили концепт „вишеструких“ тракастих Туринг машина који су користили две до пет трака. Туринг машине са више трака нису биле ништа снажније од машина с једним траком, али су помогле да се поједноставе програми.

Дакле, изричито изговарање „појединачне“ траке није потребно.

Туринг Цомплете

Ако физичка машина (попут рачунара) или виртуелна машина, која је софтвер, (попут ЈаваВМ) може да преузме било који програм и покрене га баш као Тјурингова машина, тада се та машина назива „Туринг Цомплете“. ПС: То је врста потврде.

Примери: Тјурингова комплетна Вс Тјурингова непотпуна машина

Калкулатор је добар пример Тјурингове непотпуне машине јер може да изведе само мали унапред дефинисани подскуп рачунања.

Међутим, кућни рачунар (Мац или ПЦ) је Турингова комплетна машина јер може да изврши било који прорачун који Турингова машина може учинити ако му дамо довољно меморије и времена.

„ЈаваСцрипт је Турингов комплетан“

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

Сада, ако размишљате о било ком савременом програмском језику, они такође узимају програме (које смо написали ми) као улаз и покрећу их. Даље, било који програм који се теоретски може написати за покретање Турингове машине такође може бити написан у ЈаваСцрипт-у. Дакле, ЈаваСцрипт је Турингов комплетан.

То је то!

??? Ако вам се свиђа овај пост, 1. 1. доле га додајте на Медиум и 2. поделите га на Твиттеру. Можете поново прослеђивати доњу картицу ???

Моји други постови

НАЈНОВИЈЕ: Функционално програмирање у ЈС - са практичним примерима (1. део)

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

  1. ЈаваСцрипт је Турингов комплетан - објашњен
  2. Функционално програмирање у ЈС - са практичним примерима (1. део)

ЕС6

  1. 5 ЈаваСцрипт „лоших“ делова који су поправљени у ЕС6
  2. Да ли је „класа“ у ЕС6 нови „лош“ део?

ВебПацк

  1. Вебпацк - збуњујући делови
  2. Замена веб-пакета и врућег модула [ХМР] (испод хаубе)
  3. Вебпацк-ов ХМР и Реацт-Хот-Лоадер - Приручник који недостаје

Драфт.јс

  1. Зашто Драфт.јс и зашто бисте требали да допринесете
  2. Како Драфт.јс представља обогаћене текстуалне податке

Реацт Анд Редук:

  1. Водич корак по корак за изградњу Реацт Редук апликација
  2. Водич за прављење Реацт Редук ЦРУД апликације ( апликација на 3 странице)
  3. Коришћење Миддлевареа у Реацт Редук апликацијама
  4. Додавање робусне провере обрасца за реаговање Редук апликација
  5. Обезбеђивање Реацт Редук апликација помоћу ЈВТ токена
  6. Руковање трансакционим порукама е-поште у апликацијама Реацт Редук
  7. Апликација Анатоми оф а Реацт Редук

Салесфорце

  1. Развој апликација Реацт Редук у програму Салесфорце Висуалфорце

Хвала за читање!