Википедија

Тјурингова потпуност

У теорији израчунљивости (рачунарству), систем за обраду података правила (као што је скуп инструкција рачунара, неки програмски језик, или ћелијски аутомат) је рекао да је Тјуринг потпун или рачунски универзалан ако се може користити за симулацију било које снимљене траке Тјурингове Машине . Концепт је добио име по енглеском математичару Алану Тјурингу. Класичан пример је ламбда рачун.

Уско повезан концепт је концепт Тјурингове еквиваленције - два компјутера П и К се називају еквивалентна ако П може симулирати К и К може да симулира П. Према Черч-Тјуринговој тези, која претпоставља да су Тјурингове машине најмоћније компјутерске машине, за сваки рачунар у реалном свету постоји Тјурингова машина која може да симулира своје рачунске аспекте. Универзалне Тјурингове машине могу симулирати било коју Тјурингову Машину а самим тим и рачунарске аспекте сваког могућег рачунара у реалном свету.

Да би показао да је нешто Тјуринг потпуно, довољно је да покаже да може да се користи да симулира неки Тјуринг потпун систем. На пример, императивно програмирање је Тјуринг потпуна ако има условно гранање (нпр.: "ако" и "иди" изјаве, или "гранај ако је нула" упутства. Види: Један скуп рачунарских инструкција ( OISC)) и способност да промени произвољну количину рачунарских меморијских локација (нпр. способност одржавања произвољног броја варијабли). Пошто је ово готово увек случај, већина (ако не и сви) императивни програми су Тјуринг потпуни ако се игноришу ограничења коначне меморије.

Употреба поред математике

уреди

У колоквијалној употреби, термини "Тјуринг потпун" или "Тјуринг еквивалентан" се користе да означе да било који рачунар за општу намену или рачунарски језик могу приближно да симулирају рачунарске аспекте било ког другог рачунара за општу намену или рачунарски језик.

Прави компјутери изграђени до сада су у суштини слични снимљеној траци Тјурингове Машине. Међутим, прави компјутери имају ограничене физичке ресурсе, тако да су они само  линеарно-ограничени аутомат потпуни. Насупрот томе, универзални рачунар се дефинише као уређај са Тјуринг потпуним сетом инструкција, бескрајном меморијом, и бесконачним расположивим временом.

Формалне дефиниције

уреди

У теорији израчунљивости (рачунарству), неколико уско повезаних термина користе се да опишу рачунарске снаге математичких  система (као што је апстрактна машина или програмски језик):

Тјурингова потпуност
Математички систем који може да израчуна сваку Тјурингову-рачунску функцију зове се Тјуринг потпун (или Тјуринг моћан). Алтернативно, такав систем је онај који може да симулира универзалну Тјурингову машину.
Тјуринг еквивалентан
Тјуринг-потпун систем се назива Тјуринг еквивалентан ако се свака функција која се може израчунати такође Тјуринг израчунљива; тј, да израчунава потпуно исту класу функција као и Тјурингове машине. Алтернативно, Тјуринг-еквивалентан систем је онај који може да симулира, и да буде симулиран, универзалном Тјуринговом машином. (Сви познати Тјуринг-потпуни системи су и Тјуринг еквивалентни, што додаје подршку Черч-Тјуринговој тези.)
(Рачунарска) универзалност
Систем се зове универзалним у односу на класу система ако му се могу израчунати све рачунске функције од стране система у тој класи (или може да симулира сваки од тих система). Типично, термин универзалност се прећутно користи у односу на Тјуринг-потпуну класу система. Термин "слабо универзални" се понекад користи за разликовање система (нпр. ћелијски аутомат) чија универзалност се остварује само изменом стандардне дефиниције Тјурингове машине како би укључили улазне токове са бесконачно много 1с.

Историја

уреди

Тјурингова потпуност је значајна у сваком реално временском дизајну за рачунарске уређаје да може бити симулиран од стране универзалне Тјурингове машине. Черч-Тјурингова теза гласи да је ово закон математике - да универзална Тјурингова машина може, у принципу, обављати било који обрачун да било који други рачунар може програмирати. То ништа не говори о напору потребном да напише програм, или време потребно машини за обављање обрачуна, или способностима машина које могу поседовати а који немају никакве везе са обрачуном.

Чарлс Бебиџова аналитичка машина (1830) би била прва Тјуринг-потпуна машина ако би изграђена у време када је пројектована. Бебиџ цени да је машина била у стању великих подвига обрачуна, укључујући и примитивно логичко расуђивање, али није проценио да ниједна друга машина може боље. Од 1830. до 1940. , механичке машине за рачунање, као што су шарке и мултипликаторима изграђени и побољшани, али нису могли да обављају условно грану и стога нису Тјуринг потпуна.

Крајем 19. века, Леополд Кронекер је формулисао појмове израчунљивости, дефинисањем примитивних рекурзивних функција. Ове функције се могу израчунати напамет, али нису довољне да се направи универзални рачунар, јер су инструкције које их израчунавају не дозвољавају бесконачну петљу. Почетком 20. века, Дејвид Хилберт је водио програм аксиоматизације свих математика са прецизним аксиомима и прецизним логичним правилима одузимањем које би могла да обавља машина. Убрзо је постало јасно да је мали скуп правила одбитака довољан да произведе последице било ког скупа аксиома. Ова правила су доказана од стране Курта Гедела 1930. као довољна да произведу сваку теорему. Међутим, оне ће увек доказати теореме као истинито и лажно, за аксиоматизацију није једноставнија од Пеанових аксиома.

Стварни појам рачунања је изолован убрзо након тога, почевши од Геделове теореме о непотпуности. Ове теореме показале су да су аксиомни системи ограничени када образлажу о прорачуну који закључује њихове теореме. Черч и Тјуринг су независно показали да је Хилбертов програм проналажења потпуног и конзистентног скупа аксиома који би важио за целу математику био нерешив, и тиме идентификовали некомплетност теореме. Овај рад, заједно са Геделовим радом на општим рекурзивним функцијама, утврдио да постоје скупови једноставних упутстава, која, када се ставе заједно, су у стању да производе било које рачунање. Геделов рад је показао да је појам рачунања у суштини јединствен.

Теорија израчунљивости

уреди

Први резултат теорије израчунљивости је да је немогуће уопште да се предвиди шта ће Тјуринг-комплетан програм учинити и после произвољно дуго времена. На пример, немогуће је утврдити за сваки пар програма-улаз да ли ће се програм, који ради на улазу, на крају зауставити или ће наставити заувек (види халтинг проблем). То је немогуће одредити да ли ће програм вратити "истина" или да ли ће се вратити "лаж". За сваку карактеристику евентуалне производње програма, немогуће је одредити да ли ће ова карактеристика издржати. То може да изазове проблеме у пракси приликом анализирања компјутерских програма. Један од начина да се то избегне је да изазове програм да се заустави извршење након одређеног периода времена (тајмаут), или да ограниче моћ упутства за контролу протока. Такви системи нису Тјуринг-потпуни дизајнирани.

Друга теорема показује да постоје проблеми решиви Тјуринг-потпуним језицима који се не могу решити било којим језиком само са способношћу коначних петљи (нпр, на било ком језику који гарантује сваки програм ће на крају завршити до застоја). С обзиром на гарантовану обуставу језик, рачунарску функцију која је произведена од стране Канторове дијагонале аргумента о свим рачунарским функцијама у том језику није израчунљив на том језику.

Тјурингова пророчка машина

уреди

Рачунар са приступом бескрајној траци података може бити моћнији од Тјурингове машине: на пример, трака можда садржи решење халтинг проблема или неког другог Тјуринговог-неодлучивог проблема. Таква бескрајна трака података се зове Тјурингова пророчка машина. Чак и Тјурингова пророчка машина са случајним подацима није израчунљива (са вероватноћом 1), јер постоје многи израчунљиви прорачуни али неизрачунљиви пророци. Дакле, рачунар са случајном Тјуринговом пророчком машином може израчунати ствари које Тјурингова машина не може.

Дигитална физика

уреди

Сви познати закони физике имају последице који су за израчунавање низом апроксимација на дигиталном рачунару. Хипотеза која се зове дигитална физика наводи да ово није случајно, да је то зато што је сам свемир израчунљив на универзалној Тјуринговој машини. То би значило да нема компјутера моћнијег од универзалне Тјурингове машине који могу бити физички изграђени (види Черч-Тјурингову тезу - филозофске импликације).

Примери

уреди

Рачунарски системи (алгебре, калкулуса) који се помињу као Тјуринг потпуни системи су намењени за студирање теоријског рачунарства. Они треба да буду што једноставнији, тако да би било лакше да се схвате границе рачунања. Ево неколико:

Већина програмских језика, конвенционални и неконвенционални, су Тјуринг-потпуни. То укључује:

Тјурингова потпуност је апстрактна изјава способности, а не прописивање специфичности језика који се користи за спровођење те способности. Функције се користе за постизање Тјурингове потпуности може бити сасвим другачији; Фортран системи ће користити петље конструкције или чак ГоТо на изјаве да се постигне понављање; Хаскел и Пролог, без петље скоро у потпуности, ће користити рекурзију.

Тјурингова потпуност у декларативном SQL се реализује кроз заједничку табелу рекурзивних израза. Не изненађује, процедурална проширења SQL (PLSQL, итд) су такође Тјуринг потпуна. То илуструје један од разлога зашто су релативно снажни не-Тјуринг-потпуни језици ретки: снажнији језик је у почетку, сложенији су задаци на којима се примењује и раније њен недостатак потпуности почиње да се доживљава као мана, подстицање је проширење док не буде Тјуринг потпун.

Не откуцан Ламбда рачун је Тјуринг потпун, али многи откуцани ламбда калкулуси, укључујући Систем Ф, нису. Вредност куцаних система се заснива на њиховој способности да представљају већину типичних компјутерских програма, док открива више грешака.

Правило 110 и Конвејева игра живота, оба ћелијска аутомата, су Тјуринг потпуни.

На нижем нивоу, сваки језик који може да симулира основне компоненте (логичка кола, итд) је Тјуринг потпун. Хардвер опис језици попут ВХДЛ и Верилог су Тјуринг потпуни, јер се оба користе за дизајнирање чипова од којих су модерни рачунари направљени. Мајнкрафт који је у стању да имитира логичка кола користећи свој редстоун и клип механизма, такође Тјуринг потпун.

Језици који нису Тјуринг поптуни

уреди

Постоје многи рачунарски језици који нису Тјуринг потпуни. Један такав пример је скуп регуларних језика, најчешће регуларних израза, који су генерисани у коначном аутомату. Моћнији, али још увек не Тјуринг-потпуно продужење коначних аутомата је категорија потисни аутомати и контекстно слободна граматика, које се обично користе за генерисање анализе стабла у почетној фази компилатора. Даљи примери су неке од раних верзија Пиксел Шадер језика уграђених у Direct3D и OpenGL проширења.

У комплетно функционалном програмирању програмских језика, као што су Charity и Epigram, све функције су укупне и морају се прекинути. Charity користи тип система и контроле конструкције засноване на теорији категорије, док Епиграм користи зависне врсте. Петља језика је дизајнирана тако да израчунава само функције које су примитивно рекурзивне. Све ово израчуна одговарајуће подскупове укупних израчунљивих функција, док је цео сет комплетних израчунљивих функција неизрачунљив набрајањем. Такође, пошто су све функције у овим језицима коначне, алгоритми за рекурзивне сетове набрајања не могу бити написани на овим језицима, у супротности са Тјуринговим машинама.

Иако (не откуцан) ламбда рачун је Тјуринг-потпун, просто откуцан ламбда рачун није.

Језици података

уреди

Појам Тјурингова-потпуност се не односи на језике као што су XML, HTML, JSON, YAML и S-expressions, јер се обично користе за представљање структуираних података, не описују рачунања. Они се понекад називају језицима за обележавање, или тачније као "посуда са језицима" или " језицима за описивање података". Међутим, правило 110, Тјуринг потпун ћелијски аутомат успешно је реализован у CSS-у, чиме доказује (у одређеној мери) своју Тјурингову потпуност.

Види још

уреди

Референце

уреди

Литература

уреди

Спољашње везе

уреди
Преузето из „https://sr.wiki.x.io/w/index.php?title=Тјурингова_потпуност&oldid=27028469”