Цялостност по Тюринг

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

Тясно свързана концепция е тази за Тюрингова еквивалентност – два компютъра P и Q се наричат ​​еквивалентни, ако P може да симулира Q, то и Q може да симулира P. Тезата „The Church-Тюринг“ предполага, че всяка функция, чиито стойности могат да бъдат изчислени чрез алгоритъм може да бъдат изчислени от една машина на Тюринг, и следователно ако реален компютър може да бъде симулиран от машина на Тюринг, то той е Тюрингов еквивалент на машина на Тюринг. Универсална Тюрингова машина може да се използва за симулиране на всяка машината на Тюринг и по подразбиране на изчислителните аспекти, на който и да било реален компютър.

За да докажем, че нещо е цялостно по Тюринг, е достатъчно да се докаже, че може да се използва за симулиране на някаква цялостна Тюринг система. Например, императивен език на програмиране е цялостен по Тюринг, ако има условно разклоняване (например, if и go to изявления, или „разклони в случай на нула" инструкция) и способността да променя произволно количество памет (например умението да поддържа произволен брой променливи). Тъй като това почти винаги е така, повечето (ако не всички) императивни езици са Тюринг цялостни, ако се игнорира ограничението на крайното количество памет.

История

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

Първата цялостна по Тюринг машина е щяла да бъде Аналитичният двигател на Чарлз Бабидж (1830 г.), ако е била построена, но тя остава само проект. Бабидж твърдял, че машината е в състояние да извършва изключителни постижения в изчислението, включително примитивно логическо мислене, но той не е предполагал, че никоя друга машина не може да се справи по-добре. От 1830 до 1940 г., механични сметачни машини, като например разширители и мултипликатори са били построени и подобрени, но те не са могли да изпълняват условни преходи и следователно не са били цялостни по Тюринг.

В края на 19 век, Леополд Кронекер формулира идеята за изчислимостта, дефинирайки примитивни рекурсивни функции. Тези функции могат да бъдат механично извършвани изчисления, но не биха били достатъчни, за да се направи универсален компютър, защото инструкциите които изчисляват те не позволяват един безкраен цикъл. В началото на 20 век, Давид Хилберт е достигнал до програма, която да аксиоматизира всички математически изчисления с точни аксиоми и определени логически правила на удържане, които биха могли да се извършват от една машина. Скоро става ясно, че един малък набор от правила за удържане са достатъчни, за да се възпроизведат последствията от всеки набор от аксиоми. Тези правила са били доказани от Кърт Гьодел през 1930 г., като достатъчни, за да се възпроизвежда всяка теорема. Въпреки това, те винаги ще доказват, това че някой теореми са едновременно верни и грешни за аксиоматиране не по-просто от аксиомите на Пеано.

Действителната идея за изчисление е изолирана скоро след като се появила непълната теорема на Гьодел. Тази теорема показва, че аксиоматираните системите са ограничени, когато се правят изводи за изчислението, което заключава техните теореми. Чърч и Тюринг, независимо един от друг, доказват, че проблемът на Хилберт е нерешим, като по този начин се идентифицира изчислителната сърцевина на непълната теорема. Тези резултати заедно с работата на Гьодел за общи рекурсивни функции доказват, че има групи от прости команди, които приложени заедно са в състояние да възпроизведат всякакви изчисления. Работата на Гьодел доказва, че понятието за изчисление по същество е уникално.

Извън математическо ползване

В разговорния език понятието „Цялост по Тюринг“ или „Тюринг еквивалентност“ се използва, за да се обясни това, че който и да е компютър в реалния свят с общо предназначение или в компютърния език, може приблизително да изчисли стимулирането на промени в изложението, на който и да е друг компютър в реалния свят с общо предназначение или компютърен език.

Реалните компютри, изградени, са основани на една-единствена лента на Машината на Тюринг. Следователно математически е възможно, чрез абстракция, те да бъдат експлоатирани от достатъчно голямо разстояние. Истинските компютри имат ограничени технически ресурси, така че те са автоматично праволинейно ограничени. За разлика от тях, универсалният компютър се определя като устройство с пълен набор от команди на Тюринг, безгранична памет и неизчерпаема достъпност до него.

Тюринг Oracle

Компютър с достъп до безкрайна лента данни може да е по-силен от една машина на Тюринг. Например, лентата може да съдържа решението на проблема за спиране (HALT), или някакъв друг Тюринг-нерешим проблем. Такава една безкрайна лента на данни се нарича Тюринг Oracle. Дори Тюринг Oracle с произволни данни не е изчислима (с вероятност 1), тъй като има преброим брой изчисления, но не и пребродим брой оракули. Компютър с произволен Тюринг Oracle може да изчисли неща, които една машина на Тюринг не може.

Изчислителна теория на Тюринг

Първите резултати от изчислителната теория показват, че е невъзможно да се предвиди какъв резултат ще даде Тюринг – пълна програма, за неопределено дълго време. Например, не е възможно да се определи за всеки входен чифт данни, дали програмата в крайна сметка ще спре (HALT) или ще продължи завинаги (LOOP). Невъзможно е също и да се определи дали програмата ще върне „вярно“ (true) или ще върне „невярно“ (false). Това може да доведе до проблеми в практиката, когато се анализират компютърни програми в реалния свят. Един от начините да се избегне това е да се предизвикат програми за спиране на изпълнението след определен период от време (time-out), или да се ограничи властта на инструкциите за контрол на потока. Такива системи не са Тюринг-пълни по дизайн.

Друга теорема показва, че има проблеми, решими от Тюринг-пълни езици, които не могат да бъдат решени от друг език, които имат ограничени способности (т.е., всеки език, който гарантира всяка програма, че накрая ще спре (HALT). Получавайки гарантирано спрян език, изчислената функция която е произведена от диагоналния аргумент на Кантор върху всички изчислени функции на този език не са изчислими в него.

Дигитална физика

Всички известни закони на физиката имат последици, които са изчислими от поредица от предвиждания на цифров компютър. Хипотеза, наречена цифрова физика гласи, че това не е случайно, че това е така, защото самата вселена е изчислима върху универсална Тюринг-машина. Това означава, че няма по-силен компютър, от една универсална Тюринг-машина.

Официални дефиниции

В изчислителната теория, множество тясно свързани термини, се използват за описване на изчислителната мощ на изчислителната система (като абстрактна машина или език за програмиране):

Цялостност по Тюринг

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

Еквивалентност по Тюринг

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

(Изчислителна) универсалност

Една системата се нарича универсална по отношение на клас системи, ако може да се изчисли всяка функция изчислима от системи в този клас (или може да симулира всяка от тези системи). Обикновено терминът универсалност, по подразбиране, се използва по отношение на цялостни по Тюринг клас системи. Терминът „слабо универсален“ понякога се използва, за да се разграничи система (например клетъчен автомат), чиято универсалност се постига само чрез промяна на стандартната дефиниция за Тюринговата машина, така че да включат входни потоци данни с безкрайно много 1s.

Не-цялостни по Тюринг езици

Съществуват много изчислителни езици, които не са цялостни по Тюринг. Такъв пример е множество от регулярни езици, които са генерирани от регулярни изрази, и които се разпознават от крайните автомати. По-мощно, но все пак не-цялостно по Тюринг, разширение на крайните автомати е категорията на бутащ автомат (pushdown automata) и контекстно-свободни граматики (context-free grammar), които обикновено се използват за генериране на парсващи дървета в началния етап на компилирането на програмата. Други примери включват някои от ранните версии на пиксел шейдър езиците, които са вградени в разширенията Direct3D и OpenGL.

В изцяло функционалните езици за програмиране, като например Charity и Epigram, всички функции са абсолютни и трябва да се прекратят. Charity използва система за писане и контролни конструкции, базирани на теорията за категориите, докато Epigram използва зависими типове. Езикът LOOP е проектиран така, че да изчислява само функциите, които са примитивно рекурсивни. Всички те изчисляват характерни подгрупи на абсолютно изчислимите функции, тъй като пълният набор от абсолютно изчислимите функции не може да бъде изчислимо номериран (computably enumerable). Тъй като всички функции в тези езици са абсолютни, на тях не могат да се пишат алгоритми за рекурсивно номерирани множества, в сравнение с машина на Тюринг.

Въпреки че нетипизираната ламбда функция (untyped lambda calculus) е цялостна по Тюринг, просто типизираната ламбда функция (simply typed lambda calculus) не е.

Езици за бази данни

Понятието за цялостност по Тюринг не се прилага за езици като XML, HTML, JSON (JavaScript Object Notation), YAML и S-expressions, защото обикновено се използват за представяне на структурирани данни, а не за описване на изчисления. Понякога се наричат маркиращи ​​езици, или по-правилно като „контейнер езици“ или „езици за описване на данни“. Въпреки това, Rule 110, цялостен по Тюринг клетъчен автомат, е бил успешно приложена в CSS (Cascading Style Sheets), доказвайки по този начин (до определена степен) неговата цялостност по Тюринг (в действителност не всеки е съгласен с това, например Франсис Маккейб твърди, че CSS не е цялостен по Тюринг, тъй като няма опция за дефиниране на функции).

Примери

Изчислителните системи (алгебрични, функции), които се смятат за цялостни по Тюринг са тези, които са предназначени за изучаване на теоретичните компютърни науки. Те са замислени да бъдат възможно най-прости, така че да е по-лесно да се разберат границите на изчисление. Ето някои от тях:

-Теория на автоматите

-Формална граматика (езикови генератори)

-Формален език (език за разпознаване)

-Ламбда функции

-Пост-Тюрингови машини

Повечето програмни езици, конвенционални и неконвенционални, са Тюринг цялостни. Това включва:

-Всички езици с общо предназначение в широка употреба.

-Процедурни езици за програмиране като C, Pascal.

-Обектно-ориентирани езици като CIL, Java, Smalltalk.

-Мулти-парадигмови езици като Ada, C++, Common Lisp, Object Pascal.

-Повечето езици, използващи по-малко разпространени парадигми

-Функционални езици като Lisp и Haskell.

-Езици за логическо програмиране като Prolog.

-Декларативни езици като XSLT.

-Езотерични езици за програмиране, като форма на математическо пресъздаване, в което програмистите работят за постигане на основни програмни конструкции в изключително труден, но математически цялостен по Тюринг език.

Презаписващите системи също са Тюринг-цялостни.

Цялостност по Тюринг е по-скоро абстрактно изявление за способност, отколкото определяне на специфичните особености на езика, използвани за осъществяването на тази способност. Характеристиките, използвани за постигането на тази способност, могат да са доста различни; Фортран системите биха използвали циклични конструкции или дори goto изявления за постигане на повторение; Haskell и Prolog, при които почти изцяло липсват цикли, ще използват рекурсия. Повечето програмни езици описват изчисления по структурирането на фон Нойман, което има памет (RAM и регистър) и блок за управление. Тези два елемента правят тази структура цялостна по Тюринг. Дори чисто функционалните езици са цялостни по Тюринг.

Тюринг-цялостност в декларативния SQL се постига чрез общи рекурсивни изрази. Не е изненадващо, че процедурните разширения на SQL (PLSQL и т.н.) също са цялостни по Тюринг. Това показва една от причините защо сравнително мощни не-цялостни по Тюринг езици са рядкост: колкото по-мощен е езикът първоначално, толкова по-сложни са задачите, за които се прилага и толкова по-скоро липсата му на завършеност се възприема като недостатък, което насърчава неговото разширяване, докато стане Тюринг цялостен.

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

Rule 110, Играта на живота на Конуей и двете клетъчни автомати, са Тюринг цялостни.

Игри

Много игри са цялостни по Тюринг по случайност.

• Видеоигри:
  • Conway’s Game of Life
  • Dwarf Fortress
  • Minecraft
  • Minesweeper
  • LittleBigPlanet
  • Pokemon Yellow

• Игри с карти:
  • Magic: The Gathering

Вижте също

• Изчислителна теория
• Йерархия на Чомски
• Стивън Волфрам
• Тезис на Чърч

Източници

Тази страница частично или изцяло представлява превод на страницата Turing completeness в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​