Уикипедия

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

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
KMechkov (беседа | приноси)
11 редакции
Редакция без резюме
Редакция без резюме
Ред 1:
В [[Изчислителна теория|изчислителната теория]], система от правила за манипулация на данни (като набор от инструкции на компютъра, [[Език за програмиране|програмен език]], или клетъчен автомат) се смята за цялостна по Тюринг или изчислително универсална, ако може да се използва за симулиране на която и да било еднолентова машина на Тюринг. Концепцията е наречена на името на английския математик [[Алън Тюринг]]. Класически пример е [[Анонимна функция|ламбда функцията]].
 
Тясно свързана концепция е тази за Тюрингова еквивалентност - два компютъра P и Q се наричат ​​еквивалентни, ако P може да симулира Q, то и Q може да симулира P. Тезата [[Тезис_на_Чърч|"The Church-Тюринг"]] предполага, че всяка функция, чиито стойности могат да бъдат изчислени чрез [[алгоритъм]] може да бъдат изчислени от една машина на Тюринг, и следователно ако реален компютър може да бъде симулиран от машина на Тюринг, то той е Тюрингов еквивалент на машина на Тюринг. Универсална Тюрингова машина може да се използва за симулиране на всяка машинамашината на Тюринг и по подразбиране на изчислителните аспекти, на който и да било реален компютър.
 
За да докажем, че нещо е цялостно по Тюринг, е достатъчно да се докаже, че може да се използва за симулиране на някаква цялостна Тюринг система. Например, [[Императивно програмиране|императивен език на програмиране]] е цялостен по Тюринг, ако има условно разклоняване (например, "if" и "go to" изявления, или  „разклони в случай на нула" инструкция. Виж OISC<ref>[https://en.wikipedia.org/wiki/Office_of_the_Immigration_Services_Commissioner IOSC]</ref>) и способността да променя произволно количество [[Компютърна памет|памет]] (например умението да поддържа произволен брой променливи). Тъй като това почти винаги е така, повечето (ако не всички) императивни езици са Тюринг цялостни, ако се игнорира ограничението на крайното количество памет.
Ред 17:
 
== Извън математическо ползване ==
В разговорният език понятието „Цялост по Тюринг” или „Тюринг еквивалентност” се използва, за да се обясни това, това че, който и да е компютър в реалният свят с общо предназначение или в компютърният език , може приблизително да изчисли стимулирането на промени в изложението, на който и да е друг компютър в реалният свят с общо предназначение или компютърен език.
 
Реалните компютри, изградени до ден днешен, са основани на една единствена лента на Машината на Тюринг. Следователно математически е възможно, чрез абстракция, те да бъдат експлоатирани от достатъчно голямо разстояние. Истинските компютри имат ограничени технически ресурси, така че те са автоматично праволинейно ограничени. За разлика от тях, универсалният компютър се определя като устройство с пълен набор от команди на Тюринг , безгранична памет и неизчерпаема достъпност до него.
Ред 25:
 
== Изчислителна теория на Тюринг ==
Първите резултати от изчислителната теория епоказват, че е невъзможно да се предвиди какъв резултат ще даде Тюринг- пълна програма, за неопределено дълго време. Например, не е възможно да се определи за всеки входен чифт данни, дали програмата в крайна сметка ще спре(HALT) или ще продължи завинаги(LOOP). Невъзможно е също и да се определи дали програмата ще върне „вярно“ („true“) или ще върне „“невярно(„false“)". Това може да доведе до проблеми в практиката, когато се анализират компютърни програми в реалния свят. Един от начините да се избегне това е да се предизвикат програми за спиране на изпълнението след определен период от време („time-out“), или да се ограничи властта на инструкциите за контрол на потока. Такива системи не са Тюринг-пълни по дизайн.
 
Друга теорема показва, че има проблеми, решими от Тюринг-пълни езици, които не могат да бъдат решени от друг език, които имат ограничени способности (т.е., всеки език, който гарантира всяка програма, че накрая ще спре(HALT)). Получавайки гарантирано спрян език, на изчислимаизчислената функция, която сее произвеждапроизведена от диагоналния аргумент на Кантор завърху всички изчислимиизчислени функции вна този език, не еса изчислимаизчислими нав този езикнего.
 
== Дигитална физика ==
Взето от „https://bg.wikipedia.org/wiki/Цялостност_по_Тюринг“.