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

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

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

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

 

 

Компютър с достъп до безкрайна лента данни може да е по-силен от една машина на Тюринг. Например, лентата може да съдържа решението проблема за спиране(HALT), или някакъв друг Тюринг-нерешим проблем. Такава една безкрайна лента на данни се нарича Тюринг Oracle. Дори Тюринг Oracle с произволни данни не е изчислима (с вероятност 1), тъй като има преброим брой изчисления, но не пребродим брой оракули. Да компютър с произволен Тюринг Oracle може да се изчисли неща, които една машина на Тюринг не може.

 

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

 

Друг теорема показва, че има проблеми решими от Тюринг-пълна езици, които не могат да бъдат решени от друг език, които има ограничени способности (т.е., всеки език, който гарантира всяка програма в накрая ще спре(HALT)). Получавайки гарантирано спиране език, на изчислима функция, която се произвежда от диагоналния аргумент на Кантор за всички изчислимите функции в този език не е изчислима на този език.

 

Всички известни закони на физиката имат последици, които са изчислима от поредица от предвиждания на цифров компютър. Хипотеза наречена цифрова физика гласи, че това не е случайно, че това е така, защото самата вселена е изчислима върху универсална Тюринг-машина. Това означава, че няма компютър по-силен от една универсална Тюринг-машина.