Уикипедия

Цялостност по Тюринг: Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
Редакция без резюме
Редакция без резюме
Ред 1:
В [[Изчислителна теория|изчислителната теория]], система от правила за манипулация на данни (като набор от инструкции на компютъра, [[Език за програмиране|програмен език]], или клетъчен автомат) се смята за цялостна по Тюринг или изчислително универсален, ако може да се използва за симулиране на която и да било еднолентова машина на Тюринг. Концепцията е наречена на името на английския математик [[Алън Тюринг]]. Класически пример е [[Анонимна функция|ламбда функцията]].
 
Тясно свързана концепция е тази за Тюрингова еквивалентност - два компютъра P и Q се наричат ​​еквивалентни, ако P може да симулира Q, то и Q може да симулира P. Тезата на Чърч-Тюринг предполага, че всяка функция, чиито стойности могат да бъдат изчислени чрез [[алгоритъм]] може да бъде изчислена от една машина на Тюринг, и следователно ако реален компютър може да бъде симулиран от машина на Тюринг, то той е Тюрингов еквивалент на машина на Тюринг. Универсална Тюрингова машина може да се използва за симулиране на всяка машина на Тюринг и по подразбиране на изчислителните аспекти на който и да било реален компютър.
 
За да докажедокажем, че нещо е цялостно по Тюринг, е достатъчно да се докаже, че може да се използва за симулиране на някаква цялостна Тюринг система. Например, [[Императивно програмиране|императивен език на програмиране]] е цялостен по Тюринг, ако има условно разклоняване (например, "if" и "go to" изявления, или  „разклони в случай на нула" инструкция. Виж OISC<ref>[https://en.wikipedia.org/wiki/Office_of_the_Immigration_Services_Commissioner IOSC]</ref>) и способността да променя произволно количество [[Компютърна памет|памет]] (например умението да поддържа произволен брой променливи). Тъй като това почти винаги е така, повечето (ако не всички) императивни езици са Тюринг цялостноцялостни, ако се игнорира ограничението на крайното количество памет.
 
{{обработка|изчистване на машинния превод}}
{{copyvio}}
== История ==
Цялостност по Тюринг е показател за това,  че всеки дизайн на изчислително устройство в реалният свят може да бъде симулиран,  чрез универсалната машина на Тюринг. В тезата [[Тезис_на_Чърч|"The Church-Тюринг"]] се посочва, че това е закон на математиката , който гласи, че една универсална машина Тюринг може, по правило, да извърши всички изчисления, които всеки друг програмируем компютър може. Това не е показателно за усилията, които са необходими да се напише програмата  или времето, което ще отнеме  на машината да извърши изчислението, нито за каквито и да е способности,  които машината може да притежава и нямащи нищо общо със самите изчисления.
 
Първата Тюринг-завършена машина е щяла да бъде Аналитичния двигател на [[Чарлз Бабидж]] (1830г.), ако е била построена по времето, когато е била и проектирана. Бабидж е твърдял, че машината е в състояние да извършва изключителни постижения в изчислението, включително примитивно логическо мислене, но той не е предполагал, че никоя  друга машина не може да се справи по-добре. От 1830 до 1940 г., механични изчислителни машини, като например разширители и мултипликатори са били построени и подобрени, но те не са могли да изпълнят условния преход  и следователно не са били Тюринг-завършени.
 
В края на 19 век, [[Леополд Кронекер]] формулира идеята за изчислимостта, дефинирайки примитивни [[рекурсивни функции]]<ref>[http://cpp-examples.com/singlelecture.php?id=rekursivni%20funkcii Рекурсивни функции]</ref>. Тези функции могат да бъдат механично извършвани изчисления, но не биха били достатъчни, за да се направи универсален компютър, защото инструкциите които изчисляват те не позволяват един безкраен цикъл. В началото на 20 век, [[Давид Хилберт]] е достигнал до програма, която да аксиоматизира всички математически изчисления с точни аксиоми и определени логически правила на удържане, които биха  могли да се извършват от една машина. Скоро става ясно, че един малък набор от правила за удържане са достатъчни, за да се възпроизведат последствията от всеки набор от аксиоми. Тези правила са били доказани от [[Курт Гьодел|Кърт Гьодел]] през 1930 г., като достатъчни,за да се възпроизвежда всяка теорема. Въпреки това, те винаги ще доказват , това че някой теореми са едновременно верни и грешни за аксиоматиране не по-просто от аксиомите на Пеано.
 
Действителната идея за изчисление е изолиранa скоро след , като се е появила  непълнaта теорема на Гьодел. Тази теорема показва, че аксиоматираните системите са ограничени, когато се правят изводи  за изчислението, което заключава техните теореми. Чърч  и Тюринг, независимо един от друг , доказват, че проблема на Хилбъртс е нерешим, като по този начин се идентифицира изчислителната сърцевина, на непълната теорема. Тези резултати заедно с работата на  Гьодел за общи рекурсивни функции доказват ,  че има групи от прости команди,които приложени заедно са в състояние да възпроизведат всякакви изчисления. Работата на Гьодел доказва, че понятието за изчисление  по същество е  уникално.
 
== Извън математическо ползване ==
В разговорният език , понятието „Цялост по Тюринг” или „Тюринг еквивалентност” се използва, за да се обясни , това че , който и да е компютър в реалният свят с общо предназначение или в компютърният език , може приблизително да изчисли стимулирането на промени в изложението, на който и да е друг компютър в реалният свят с общо предназначение или компютърен език .
 
Реалните компютри, изградени до ден днешен, са основани на една единствена лента на Машината на Тюринг;. Следователно математически е възможно , чрез абстракция, те да бъдат експлоатирани от достатъчно голямо разстояние. Както и да е , истинскитеИстинските компютри имат ограничени технически ресурси , така че те са автоматично праволинейно ограничени. За разлика от тях, универсалният компютър се определя като устройство с пълен набор от команди на Тюринг , безгранична памет и неизчерпаема достъпност до него.
 
== Тюринг Oracle ==
Компютър с достъп до безкрайна лента данни може да е по-силен от една машина на Тюринг. Например, лентата може да съдържа решението на проблема за спиране(HALT), или някакъв друг Тюринг-нерешим проблем. Такава една безкрайна лента на данни се нарича Тюринг Oracle<ref>[https://en.wikipedia.org/wiki/Oracle_machine Oracle machine]</ref>. Дори Тюринг 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, YAML и S-expressions, защото обикновено се използват за представяне на структурирани данни, а не за описване на изчисления. Понякога се наричат [[Маркиращ език|маркиращи ​​езици]], или по-правилно като "контейнер езици" или " езици за описване на данни". Въпреки това, Rule 110<ref>[https://en.wikipedia.org/wiki/Rule_110 Rule 110]</ref>, цялостен по Тюринг клетъчен автомат, е бил успешно приложена в CSS<ref>[https://bg.wikipedia.org/wiki/CSS CSS]</ref>(Cascading Style Sheets), доказвайки по този начин (до определена степен) неговата цялостност по Тюринг (в действителност не всеки е съгласен с това, например Франсис Маккейб твърди, че CSS не е цялостен по Тюринг, тъй като няма опция за дефиниране на функции).
 
== Примери ==
Ред 92:
Презаписващите системи също са Тюринг-цялостни.
 
Цялостност по Тюринг е по-скоро абстрактно изявление за способност, отколкото определяне на специфичните особености на езика, използвани за осъществяването на тази способност. Характеристиките, използвани за постигането на тази способност, могат да са доста различни; [[FORTRAN|Фортран]] системите биха използвали циклични конструкции или дори “goto” изявления за постигане на повторение; Haskell и Prolog, при които почти изцяло липсват цикли, ще използват [[рекурсия]]. Повечето програмни езици описват изчисления по структурирането на фон Нойман, което има памет (RAM<ref>[https://bg.wikipedia.org/wiki/%D0%9E%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0_%D0%BF%D0%B0%D0%BC%D0%B5%D1%82#RAM RAM]</ref> и регистър) и блок за управление. Тези два елемента правят тази структура цялостна по Тюринг. Дори чисто [[Функционално програмиране|функционалните езици]] са цялостни по Тюринг.
 
Тюринг -цялостност в декларативния [[SQL]] се постига чрез общи рекурсивни изрази. Не е изненадващо, че процедурните разширения на SQL (PLSQL и т.н.) също са цялостни по Тюринг. Това показва една от причините защо сравнително мощни не-цялостни по Тюринг езици са рядкост: колкото по-мощен е езикът първоначално, толкова по-сложни са задачите, за които се прилага и толкова по-скоро липсата му на завършеност се възприема като недостатък, което насърчава неговото разширяване, докато стане Тюринг цялостен.
 
Нетипизираните [[Анонимна функция|ламбда функции]] са цялостни по Тюринг, но много от типизираните, включително System F, не са. Стойността на типизираните системи се базира на умението им да представят повечето компютърни програми и едновременно с това да засичат повече грешки.
 
Rule 110 и, [[Живот (игра)|Играта на живота на Конуей]], и двете клетъчни автомати, са Тюринг цялостни.
 
=== Игри ===
Много игри са цялостни по Тюринг по случайност.
 
* Видео игри:
 
-[[Живот (игра)|Conway’s Game of Life]]
Ред 117:
-[[:en:Pokémon_Yellow|Pokemon Yellow]]
 
* Игри с карти:
 
-[[Magic: The Gathering]]
Взето от „https://bg.wikipedia.org/wiki/Цялостност_по_Тюринг“.