Цялостност по Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
Редакция без резюме |
||
Ред 56:
=== Езици за бази данни ===
Понятието за цялостност по Тюринг не се прилага за езици като XML, HTML, JSON, YAML и S-expressions, защото обикновено се използват за представяне на структурирани данни, а не за описване на изчисления. Понякога се наричат [[Маркиращ език|маркиращи езици]], или по-правилно като "контейнер езици" или " езици за описване на данни". Въпреки това, Rule 110, цялостен по Тюринг клетъчен автомат, е бил успешно приложена в CSS(Cascading Style Sheets), доказвайки по този начин (до определена степен) неговата цялостност по Тюринг (в действителност не всеки е съгласен с това, например Франсис Маккейб твърди, че CSS не е цялостен по Тюринг, тъй като няма опция за дефиниране на функции).
== Примери ==
Изчислителните системи (алгебрични, функции), които се смятат за цялостни по Тюринг са тези, които са предназначени за изучаване на теоретичните компютърни науки. Те са замислени да бъдат възможно най-прости, така че да е по-лесно да се разберат границите на изчисление. Ето някои от тях:
-Теория на автоматите
-Формална граматика (езикови генератори)
-[[Формален език]] (език за разпознаване)
-[[Анонимна функция|Ламбда функции]]
-Пост-Тюрингови машини
Повечето [[Език за програмиране|програмни езици]], конвенционални и неконвенционални, са Тюринг цялостни. Това включва:
-Всички езици с общо предназначение в широка употреба.
-Процедурни езици за програмиране като [[C (език за програмиране)|C]], [[Паскал (език за програмиране)|Pascal]].
-[[Обектно-ориентирано програмиране|Обектно-ориентирани]] езици като CIL, [[Java]], [[Smalltalk]].
-Мулти-[[Парадигма на програмиране|парадигмови]] езици като [[Ada]], [[C++]], Common Lisp, Object Pascal.
-Повечето езици, използващи по-малко разпространени парадигми
-[[Функционално програмиране|Функционални езици]] като [[Lisp (език за програмиране)|Lisp]] и [[Haskell]].
-Езици за [[логическо програмиране]] като [[Пролог (език за програмиране)|Prolog]].
-Декларативни езици като [[XSLT]].
-Езотерични езици за програмиране, като форма на математическо пресъздаване, в което програмистите работят за постигане на основни програмни конструкции в изключително труден, но математически цялостен по Тюринг език.
Презаписващите системи също са Тюринг-цялостни.
Цялостност по Тюринг е по-скоро абстрактно изявление за способност, отколкото определяне на специфичните особености на езика, използвани за осъществяването на тази способност. Характеристиките, използвани за постигането на тази способност могат да са доста различни; [[FORTRAN|Фортран]] системите биха използвали циклични конструкции или дори “goto” изявления за постигане на повторение; Haskell и Prolog, при които почти изцяло липсват цикли, ще използват [[рекурсия]]. Повечето програмни езици описват изчисления по структурирането на фон Нойман, което има памет (RAM и регистър) и блок за управление. Тези два елемента правят тази структура цялостна по Тюринг. Дори чисто [[Функционално програмиране|функционалните езици]] са цялостни по Тюринг.
Тюринг цялостност в декларативния [[SQL]] се постига чрез общи рекурсивни изрази. Не е изненадващо, че процедурните разширения на SQL (PLSQL и т.н.) също са цялостни по Тюринг. Това показва една от причините защо сравнително мощни не-цялостни по Тюринг езици са рядкост: колкото по-мощен е езикът първоначално, толкова по-сложни са задачите, за които се прилага и толкова по-скоро липсата му на завършеност се възприема като недостатък, което насърчава неговото разширяване, докато стане Тюринг цялостен.
Нетипизираните [[Анонимна функция|ламбда функции]] са цялостни по Тюринг, но много от типизираните, включително System F, не са. Стойността на типизираните системи се базира на умението им да представят повечето компютърни програми и едновременно с това да засичат повече грешки.
Rule 110 и [[Живот (игра)|Играта на живота на Конуей]], и двете клетъчни автомати, са Тюринг цялостни.
Игри
Много игри са цялостни по Тюринг по случайност.
Видео игри:
-[[Живот (игра)|Conway’s Game of Life]]
-[[:en:Dwarf_Fortress|Dwarf Fortress]]
-[[Minecraft]]
-[[Minesweeper (Windows)|Minesweeper]]
-[[:en:LittleBigPlanet|LittleBigPlanet]]
-[[:en:Pokémon_Yellow|Pokemon Yellow]]
Игри с карти:
-[[Magic: The Gathering]]
{{Превод от|en|Turing completeness|712483647}}
| |||