Цялостност по Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
мРедакция без резюме |
||
Ред 1:
В [[Изчислителна теория|изчислителната теория]], система от правила за манипулация на данни (като набор от инструкции на компютъра, [[Език за програмиране|програмен език]], или клетъчен автомат) се смята за цялостна по Тюринг или изчислително
Тясно свързана концепция е тази за Тюрингова еквивалентност - два компютъра P и Q се наричат еквивалентни, ако P може да симулира Q, то и Q може да симулира P. Тезата на Чърч-Тюринг предполага, че всяка функция, чиито стойности могат да бъдат изчислени чрез [[алгоритъм]] може да бъде изчислена от една машина на Тюринг, и следователно ако реален компютър може да бъде симулиран от машина на Тюринг, то той е Тюрингов еквивалент на машина на Тюринг. Универсална Тюрингова машина може да се използва за симулиране на всяка машина на Тюринг и по подразбиране на изчислителните аспекти на който и да било реален компютър.
| |||