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

{{обработка|проверка на термините, изчистване на машинния превод}}

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

За да докажем, че нещо е цялостно по Тюринг, е достатъчно да се докаже, че може да се използва за симулиране на някаква цялостна Тюринг система. Например, [[Императивно програмиране|императивен език на програмиране]] е цялостен по Тюринг, ако има условно разклоняване (например, "if"„if“ и "go„go to"to“ изявления, или  „разклони в случай на нула" инструкция. Виж OISC<ref>[https://en.wikipedia.org/wiki/Office_of_the_Immigration_Services_Commissioner IOSC]</ref>) и способността да променя произволно количество [[Компютърна памет|памет]] (например умението да поддържа произволен брой променливи). Тъй като това почти винаги е така, повечето (ако не всички) императивни езици са Тюринг цялостни, ако се игнорира ограничението на крайното количество памет.

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

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

В края на 19 век, [[Леополд Кронекер]] формулира идеята за изчислимостта, дефинирайки примитивни [[рекурсивни функции]]<ref>[http://cpp-examples.com/singlelecture.php?id=rekursivni%20funkcii Рекурсивни функции]</ref>. Тези функции могат да бъдат механично извършвани изчисления, но не биха били достатъчни, за да се направи универсален компютър, защото инструкциите които изчисляват те не позволяват един безкраен цикъл. В началото на 20 век, [[Давид Хилберт]] е достигнал до програма, която да аксиоматизира всички математически изчисления с точни аксиоми и определени логически правила на удържане, които биха  могли да се извършват от една машина. Скоро става ясно, че един малък набор от правила за удържане са достатъчни, за да се възпроизведат последствията от всеки набор от аксиоми. Тези правила са били доказани от [[Курт Гьодел|Кърт Гьодел]] през 1930 г., като достатъчни, за да се възпроизвежда всяка теорема. Въпреки това, те винаги ще доказват , това че някой теореми са едновременно верни и грешни за аксиоматиране не по-просто от аксиомите на Пеано.

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

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

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

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

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

Понятието за цялостност по Тюринг не се прилага за езици като [[XML]], [[HTML]], [[JSON| JSON (JavaScript Object Notation)]], 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 не е цялостен по Тюринг, тъй като няма опция за дефиниране на функции).

Цялостност по Тюринг е по-скоро абстрактно изявление за способност, отколкото определяне на специфичните особености на езика, използвани за осъществяването на тази способност. Характеристиките, използвани за постигането на тази способност, могат да са доста различни; [[FORTRAN|Фортран]] системите биха използвали циклични конструкции или дори “goto”„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> и регистър) и блок за управление. Тези два елемента правят тази структура цялостна по Тюринг. Дори чисто [[Функционално програмиране|функционалните езици]] са цялостни по Тюринг.

* [[Стивън Волфрам]] - – [[:en:A New Kind of Science|A New Kind of Science]]

== ПрепраткиИзточници ==