У теорији израчунљивости (рачунарству), систем за обраду података правила (као што је скуп инструкција рачунара, неки програмски језик, или ћелијски аутомат) је рекао да је Тјуринг потпун или рачунски универзалан ако се може користити за симулацију било које снимљене траке Тјурингове Машине . Концепт је добио име по енглеском математичару Алану Тјурингу. Класичан пример је ламбда рачун.
Уско повезан концепт је концепт Тјурингове еквиваленције - два компјутера П и К се називају еквивалентна ако П може симулирати К и К може да симулира П. Према Черч-Тјуринговој тези, која претпоставља да су Тјурингове машине најмоћније компјутерске машине, за сваки рачунар у реалном свету постоји Тјурингова машина која може да симулира своје рачунске аспекте. Универзалне Тјурингове машине могу симулирати било коју Тјурингову Машину а самим тим и рачунарске аспекте сваког могућег рачунара у реалном свету.
Да би показао да је нешто Тјуринг потпуно, довољно је да покаже да може да се користи да симулира неки Тјуринг потпун систем. На пример, императивно програмирање је Тјуринг потпуна ако има условно гранање (нпр.: "ако" и "иди" изјаве, или "гранај ако је нула" упутства. Види: Један скуп рачунарских инструкција ( OISC)) и способност да промени произвољну количину рачунарских меморијских локација (нпр. способност одржавања произвољног броја варијабли). Пошто је ово готово увек случај, већина (ако не и сви) императивни програми су Тјуринг потпуни ако се игноришу ограничења коначне меморије.
У колоквијалној употреби, термини "Тјуринг потпун" или "Тјуринг еквивалентан" се користе да означе да било који рачунар за општу намену или рачунарски језик могу приближно да симулирају рачунарске аспекте било ког другог рачунара за општу намену или рачунарски језик.
Прави компјутери изграђени до сада су у суштини слични снимљеној траци Тјурингове Машине. Међутим, прави компјутери имају ограничене физичке ресурсе, тако да су они само линеарно-ограничени аутомат потпуни. Насупрот томе, универзални рачунар се дефинише као уређај са Тјуринг потпуним сетом инструкција, бескрајном меморијом, и бесконачним расположивим временом.
У теорији израчунљивости (рачунарству), неколико уско повезаних термина користе се да опишу рачунарске снаге математичких система (као што је апстрактна машина или програмски језик):
- Тјурингова потпуност
- Математички систем који може да израчуна сваку Тјурингову-рачунску функцију зове се Тјуринг потпун (или Тјуринг моћан). Алтернативно, такав систем је онај који може да симулира универзалну Тјурингову машину.
- Тјуринг еквивалентан
- Тјуринг-потпун систем се назива Тјуринг еквивалентан ако се свака функција која се може израчунати такође Тјуринг израчунљива; тј, да израчунава потпуно исту класу функција као и Тјурингове машине. Алтернативно, Тјуринг-еквивалентан систем је онај који може да симулира, и да буде симулиран, универзалном Тјуринговом машином. (Сви познати Тјуринг-потпуни системи су и Тјуринг еквивалентни, што додаје подршку Черч-Тјуринговој тези.)
- (Рачунарска) универзалност
- Систем се зове универзалним у односу на класу система ако му се могу израчунати све рачунске функције од стране система у тој класи (или може да симулира сваки од тих система). Типично, термин универзалност се прећутно користи у односу на Тјуринг-потпуну класу система. Термин "слабо универзални" се понекад користи за разликовање система (нпр. ћелијски аутомат) чија универзалност се остварује само изменом стандардне дефиниције Тјурингове машине како би укључили улазне токове са бесконачно много 1с.
Тјурингова потпуност је значајна у сваком реално временском дизајну за рачунарске уређаје да може бити симулиран од стране универзалне Тјурингове машине. Черч-Тјурингова теза гласи да је ово закон математике - да универзална Тјурингова машина може, у принципу, обављати било који обрачун да било који други рачунар може програмирати. То ништа не говори о напору потребном да напише програм, или време потребно машини за обављање обрачуна, или способностима машина које могу поседовати а који немају никакве везе са обрачуном.
Чарлс Бебиџова аналитичка машина (1830) би била прва Тјуринг-потпуна машина ако би изграђена у време када је пројектована. Бебиџ цени да је машина била у стању великих подвига обрачуна, укључујући и примитивно логичко расуђивање, али није проценио да ниједна друга машина може боље. Од 1830. до 1940. , механичке машине за рачунање, као што су шарке и мултипликаторима изграђени и побољшани, али нису могли да обављају условно грану и стога нису Тјуринг потпуна.
Крајем 19. века, Леополд Кронекер је формулисао појмове израчунљивости, дефинисањем примитивних рекурзивних функција. Ове функције се могу израчунати напамет, али нису довољне да се направи универзални рачунар, јер су инструкције које их израчунавају не дозвољавају бесконачну петљу. Почетком 20. века, Дејвид Хилберт је водио програм аксиоматизације свих математика са прецизним аксиомима и прецизним логичним правилима одузимањем које би могла да обавља машина. Убрзо је постало јасно да је мали скуп правила одбитака довољан да произведе последице било ког скупа аксиома. Ова правила су доказана од стране Курта Гедела 1930. као довољна да произведу сваку теорему. Међутим, оне ће увек доказати теореме као истинито и лажно, за аксиоматизацију није једноставнија од Пеанових аксиома.
Стварни појам рачунања је изолован убрзо након тога, почевши од Геделове теореме о непотпуности. Ове теореме показале су да су аксиомни системи ограничени када образлажу о прорачуну који закључује њихове теореме. Черч и Тјуринг су независно показали да је Хилбертов програм проналажења потпуног и конзистентног скупа аксиома који би важио за целу математику био нерешив, и тиме идентификовали некомплетност теореме. Овај рад, заједно са Геделовим радом на општим рекурзивним функцијама, утврдио да постоје скупови једноставних упутстава, која, када се ставе заједно, су у стању да производе било које рачунање. Геделов рад је показао да је појам рачунања у суштини јединствен.
Први резултат теорије израчунљивости је да је немогуће уопште да се предвиди шта ће Тјуринг-комплетан програм учинити и после произвољно дуго времена. На пример, немогуће је утврдити за сваки пар програма-улаз да ли ће се програм, који ради на улазу, на крају зауставити или ће наставити заувек (види халтинг проблем). То је немогуће одредити да ли ће програм вратити "истина" или да ли ће се вратити "лаж". За сваку карактеристику евентуалне производње програма, немогуће је одредити да ли ће ова карактеристика издржати. То може да изазове проблеме у пракси приликом анализирања компјутерских програма. Један од начина да се то избегне је да изазове програм да се заустави извршење након одређеног периода времена (тајмаут), или да ограниче моћ упутства за контролу протока. Такви системи нису Тјуринг-потпуни дизајнирани.
Друга теорема показује да постоје проблеми решиви Тјуринг-потпуним језицима који се не могу решити било којим језиком само са способношћу коначних петљи (нпр, на било ком језику који гарантује сваки програм ће на крају завршити до застоја). С обзиром на гарантовану обуставу језик, рачунарску функцију која је произведена од стране Канторове дијагонале аргумента о свим рачунарским функцијама у том језику није израчунљив на том језику.
Рачунар са приступом бескрајној траци података може бити моћнији од Тјурингове машине: на пример, трака можда садржи решење халтинг проблема или неког другог Тјуринговог-неодлучивог проблема. Таква бескрајна трака података се зове Тјурингова пророчка машина. Чак и Тјурингова пророчка машина са случајним подацима није израчунљива (са вероватноћом 1), јер постоје многи израчунљиви прорачуни али неизрачунљиви пророци. Дакле, рачунар са случајном Тјуринговом пророчком машином може израчунати ствари које Тјурингова машина не може.
Сви познати закони физике имају последице који су за израчунавање низом апроксимација на дигиталном рачунару. Хипотеза која се зове дигитална физика наводи да ово није случајно, да је то зато што је сам свемир израчунљив на универзалној Тјуринговој машини. То би значило да нема компјутера моћнијег од универзалне Тјурингове машине који могу бити физички изграђени (види Черч-Тјурингову тезу - филозофске импликације).
Рачунарски системи (алгебре, калкулуса) који се помињу као Тјуринг потпуни системи су намењени за студирање теоријског рачунарства. Они треба да буду што једноставнији, тако да би било лакше да се схвате границе рачунања. Ево неколико:
- Теорија аутомата
- Формална граматика (генератори језика)
- Формални језик (препознавач језика)
- Ламбда рачун
- Пост-Тјурингове машине
Већина програмских језика, конвенционални и неконвенционални, су Тјуринг-потпуни. То укључује:
- Сви језици опште намене у широкој употреби.
- Језици процедуралног програмирања као што су C , Паскал.
- Језици објектно-оријентисаног програмирања као што су CIL, Јава, Smalltalk.
- Језици програмске парадигме као што су Ада, C++, Common Lisp, Object Pascal.
- Већина језика који користе мање заједничких парадигми:
- Језици функционалног програмирања као што су Lisp and Haskell.
- Језици логичног програмирања као што је Prolog.
- Декларативни језици као што је XSLT.
- Езотерични програмски језици облик математичке рекреације у којој програмери раде како да постигну основне програмске конструкције у изузетно тешком, али математички Тјуринг-еквивалентном језику.
- Систем преписивања
Тјурингова потпуност је апстрактна изјава способности, а не прописивање специфичности језика који се користи за спровођење те способности. Функције се користе за постизање Тјурингове потпуности може бити сасвим другачији; Фортран системи ће користити петље конструкције или чак ГоТо на изјаве да се постигне понављање; Хаскел и Пролог, без петље скоро у потпуности, ће користити рекурзију.
Тјурингова потпуност у декларативном SQL се реализује кроз заједничку табелу рекурзивних израза. Не изненађује, процедурална проширења SQL (PLSQL, итд) су такође Тјуринг потпуна. То илуструје један од разлога зашто су релативно снажни не-Тјуринг-потпуни језици ретки: снажнији језик је у почетку, сложенији су задаци на којима се примењује и раније њен недостатак потпуности почиње да се доживљава као мана, подстицање је проширење док не буде Тјуринг потпун.
Не откуцан Ламбда рачун је Тјуринг потпун, али многи откуцани ламбда калкулуси, укључујући Систем Ф, нису. Вредност куцаних система се заснива на њиховој способности да представљају већину типичних компјутерских програма, док открива више грешака.
Правило 110 и Конвејева игра живота, оба ћелијска аутомата, су Тјуринг потпуни.
На нижем нивоу, сваки језик који може да симулира основне компоненте (логичка кола, итд) је Тјуринг потпун. Хардвер опис језици попут ВХДЛ и Верилог су Тјуринг потпуни, јер се оба користе за дизајнирање чипова од којих су модерни рачунари направљени. Мајнкрафт који је у стању да имитира логичка кола користећи свој редстоун и клип механизма, такође Тјуринг потпун.
Постоје многи рачунарски језици који нису Тјуринг потпуни. Један такав пример је скуп регуларних језика, најчешће регуларних израза, који су генерисани у коначном аутомату. Моћнији, али још увек не Тјуринг-потпуно продужење коначних аутомата је категорија потисни аутомати и контекстно слободна граматика, које се обично користе за генерисање анализе стабла у почетној фази компилатора. Даљи примери су неке од раних верзија Пиксел Шадер језика уграђених у Direct3D и OpenGL проширења.
У комплетно функционалном програмирању програмских језика, као што су Charity и Epigram, све функције су укупне и морају се прекинути. Charity користи тип система и контроле конструкције засноване на теорији категорије, док Епиграм користи зависне врсте. Петља језика је дизајнирана тако да израчунава само функције које су примитивно рекурзивне. Све ово израчуна одговарајуће подскупове укупних израчунљивих функција, док је цео сет комплетних израчунљивих функција неизрачунљив набрајањем. Такође, пошто су све функције у овим језицима коначне, алгоритми за рекурзивне сетове набрајања не могу бити написани на овим језицима, у супротности са Тјуринговим машинама.
Иако (не откуцан) ламбда рачун је Тјуринг-потпун, просто откуцан ламбда рачун није.
Језици података
Појам Тјурингова-потпуност се не односи на језике као што су XML, HTML, JSON, YAML и S-expressions, јер се обично користе за представљање структуираних података, не описују рачунања. Они се понекад називају језицима за обележавање, или тачније као "посуда са језицима" или " језицима за описивање података". Међутим, правило 110, Тјуринг потпун ћелијски аутомат успешно је реализован у CSS-у, чиме доказује (у одређеној мери) своју Тјурингову потпуност.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
