Цялостност по Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м замяна на чужда езикова препратка |
м - ден днешен; козметични промени |
||
Ред 3:
В [[Изчислителна теория|изчислителната теория]], система от правила за манипулация на данни (като набор от инструкции на компютъра, [[Език за програмиране|програмен език]], или клетъчен автомат) се смята за цялостна по Тюринг или изчислително универсална, ако може да се използва за симулиране на която и да било еднолентова машина на Тюринг. Концепцията е наречена на името на английския математик [[Алън Тюринг]]. Класически пример е [[Анонимна функция|ламбда функцията]].
Тясно свързана концепция е тази за Тюрингова еквивалентност – два компютъра P и Q се наричат еквивалентни, ако P може да симулира Q, то и Q може да симулира P. Тезата [[
За да докажем, че нещо е цялостно по Тюринг, е достатъчно да се докаже, че може да се използва за симулиране на някаква цялостна Тюринг система. Например, [[Императивно програмиране|императивен език на програмиране]] е цялостен по Тюринг, ако има условно разклоняване (например, „if“ и „go to“ изявления, или „разклони в случай на нула" инструкция. Виж OISC<ref>[https://en.wikipedia.org/wiki/Office_of_the_Immigration_Services_Commissioner IOSC]</ref>) и способността да променя произволно количество [[Компютърна памет|памет]] (например умението да поддържа произволен брой променливи). Тъй като това почти винаги е така, повечето (ако не всички) императивни езици са Тюринг цялостни, ако се игнорира ограничението на крайното количество памет.
== История ==
Цялостност по Тюринг е показател за това, че всеки дизайн на изчислително устройство в реалният свят може да бъде симулиран, чрез универсалната [[машина на Тюринг]]. В [[
Първата цялостна по Тюринг машина е щяла да бъде ''Аналитичният двигател'' на [[Чарлз Бабидж]] (1830 г.), ако е била построена, но тя остава само проект. Бабидж твърдял, че машината е в състояние да извършва изключителни постижения в изчислението, включително примитивно логическо мислене, но той не е предполагал, че никоя друга машина не може да се справи по-добре. От 1830 до 1940 г., механични сметачни машини, като например разширители и мултипликатори са били построени и подобрени, но те не са могли да изпълняват условни преходи и следователно не са били цялостни по Тюринг.
Ред 19:
В разговорният език понятието „Цялост по Тюринг“ или „Тюринг еквивалентност“ се използва, за да се обясни това, че който и да е компютър в реалният свят с общо предназначение или в компютърният език, може приблизително да изчисли стимулирането на промени в изложението, на който и да е друг компютър в реалният свят с общо предназначение или компютърен език.
Реалните компютри, изградени
== Тюринг Oracle ==
Ред 52:
=== Езици за бази данни ===
Понятието за цялостност по Тюринг не се прилага за езици като [[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>[
== Примери ==
Ред 89:
Презаписващите системи също са Тюринг-цялостни.
Цялостност по Тюринг е по-скоро абстрактно изявление за способност, отколкото определяне на специфичните особености на езика, използвани за осъществяването на тази способност. Характеристиките, използвани за постигането на тази способност, могат да са доста различни; [[FORTRAN|Фортран]] системите биха използвали циклични конструкции или дори „goto“ изявления за постигане на повторение; Haskell и Prolog, при които почти изцяло липсват цикли, ще използват [[рекурсия]]. Повечето програмни езици описват изчисления по структурирането на фон Нойман, което има памет (RAM<ref>[
Тюринг-цялостност в декларативния [[SQL]] се постига чрез общи рекурсивни изрази. Не е изненадващо, че процедурните разширения на SQL (PLSQL и т.н.) също са цялостни по Тюринг. Това показва една от причините защо сравнително мощни не-цялостни по Тюринг езици са рядкост: колкото по-мощен е езикът първоначално, толкова по-сложни са задачите, за които се прилага и толкова по-скоро липсата му на завършеност се възприема като недостатък, което насърчава неговото разширяване, докато стане Тюринг цялостен.
Ред 124:
** [[Principle of Computational Equivalence]]
* [[Тезис на Чърч]]
* [[
* [[Algorithmic information theory]]
* [[Inner loop]]
| |||