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

У теоријској рачунарској науци и математици, теорија израчунљивости је грана рачунарства која разматра могу ли се и с којом ефикасношћу решити проблеми користећи рачунар. Поље је подељено у три главне гране: теорију аутомата и језике, теорију израчунљивости и теорију комплексности, с тим да све гране изучавају формалне моделе рачунања.^[1]

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

Како би ригорозно проучавали рачунање, рачунарски научници користе математичке апстракције, моделе рачунања. Неколико је формулација у употреби, али најчешће испитивана је Турингова машина.^[2] Турингова машина се може схватити као лични рачунар опремљен меморијом бесконачног капацитета, иако може меморији приступати у малим дискретним деловима. Информатичари проучавају Турингову машину јер је она једноставна за формулацију и може бити анализирана и коришћена у доказивању резултата јер представља оно што многи сматрају најмоћнијим могућим „разумним“ моделом рачунања.^[3] Иако се захтев за меморијом бесконачног капацитета може схватити као нефизикалан, за сваки стварно решен проблем Туринговом машином коришћена меморија ће увек бити коначна,^[4] па сваки проблем који реши Турингова машина може решити и персонални рачунар са довољно уграђене меморије.

Гране

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

Теорија израчунљивости се примарно бави питањем је ли проблем уопште решив на рачунару. Проблем заустављања је један од најважнијих резултата у теорији израчунљивости, јер представља пример конкретног проблема којег је и лако формулисати и немогуће решити користећи Турингову машину.^[5] Већи је део теорије израчунљивости изграђен око резултата проблема заустављања.

Још један важан корак у теорији израчунљивости је била Рајсова теорема, који наводи да је за сва нетривијална својства парцијалних функција, неизвесно да ли Турингова машина израчунава парцијалне функције са тим својством.^[6]

Теорија израчунљивости је уско везана са граном математичке логике званом теорија рекурзије, која отклања ограничење проучавања само модела рачунања који су блиски оним физикално остваривима.^[7] Многи математичари и рачунски теоретичари који проучавају теорију рекурзије ће је назвати теоријом израчунљивости. Не постоји стварна разлика између двају поља.

Теорија комплексности

Теорија комплексности разматра не само може ли се проблем уопште решити на рачунару, већ и колико ефиксно може бити решен. Два главна аспекта су посматрана: временска сложеност и просторна сложеност, који респективно представљају број корака потребан да се рачунање обави, те количину меморије потребну за обављање рачунања.

Како би анализирали колико времена и простора дати алгоритам захтева, истраживачи изражавају време и простор захтеван за решавање проблема као функцију улазног проблема. На пример, проналажење неког појединог броја у дугој листи бројева постаје све теже како та листа расте. Ако кажемо да постоји н бројева у листи, тада, уколико листа није предсортирана или на неки начин индексирана, морамо испитати сваки број како бисмо пронашли број који тражимо. Стога кажемо да, како би решио овај проблем, рачунар мора обавити број корака који расте линеарно у односу на величину проблема.

Како би поједноставили овај проблем, истраживачи су прихватили велику О нотацију, која дозвољава поређење функција на начин који осигурава да појединачни аспекти конструкције машине не морају бити разматрани, већ само асимптотско понашање како проблеми постају све већи. Зато се у претходном примеру може рећи да проблем захтева н корака за решавање.

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

Друге формалне дефиниције рачунања

Осим Турингове машине, користе се и други модели рачунања као што су: ламбда рачун, комбинаторска логика, μ-рекурзивна функција, Марковљев алгоритам, Регистарска машина, П′′,

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

Комбинаторна логика: је концепт који има много сличности са $\lambda$ -рачуном, али постоје и важне разлике (нпр. комбинатор фиксне тачке Y у комбинаторној логици има нормалну форму, али не и у $\lambda$ -рачуну). Комбинаторна је логика развијена са великим амбицијама: разумевање природе парадокса, чињења основна математике економичнијима (концептуално), те елиминисање нотације варијабли (те тако осветљавајући њихову улогу у математици).

μ-рекурзивне функције: рачунање је μ-рекурзивна функција, тј. њен дефинирајући след, било која улазна вредност/вредности те след рекурзивних функција које се појављују у дефинирајућем следу са улазима и излазима. Стога, ако се у дефинирајућем следу рекурзивне функције $f(x)$ појављују $g(x)$ и $h(x,y)$ , тада се могу појавити термини облика 'g(5)=7' или 'h(3,2)=10'. Сваки унос у овом следу треба бити апликација основне функције или следити из горњих уноса користећи композицију функција, примитивну рекурзију или μ-рекурзију. На пример, ако је $f(x)=h(x,g(x))$ , тада да би се појавио 'f(5)=3', горе се морају појавити термини попут 'g(5)=6' i 'h(3,6)=3'. Рачунање терминира само ако коначни термин даје вредност рекурзивне функције примењене на улазе.

Марковљев алгоритам: систем за преписивање стринга који користи правила слична граматичким како би деловао над стринговима симбола.

Регистарска машина: је теоретски занимљива идеализација рачунара. Постоји више варијанти. У већини од њих, сваки регистар може да садржи природни број (неограничене величине), док су саме инструкције једноставне (обично тек неколицина њих), па нпр. постоје само декрементирање (комбиновано са условним скоком) и инкрементирање (и заустављање). Недостатак бесконачне (или динамички растуће) спољашње меморије (попут оне у Туринговим машинама) се може шватити као замена њене улоге техникама Геделовог обројавања.^[8] Чињеница да сваки регистар садржи природни број допушта могућност представљања сложених конструката (нпр. низа, матрице итд.) одговарајућим великим природним бројем - неједнозначност и представљања и интерпретирања може бити успостављена на основама ових техника заснованих на теорији бројева.

P′′: Попут Турингових машина, P′′ користи бесконачну траку симбола (без случајног приступа) и поприлично минималистички скуп инструкција.^[9]^[10] Али ове су инструкције врло различите, те стога, за разлику од Турингових машина, за P′′ није неопходно одржавати различито стање, јер сву функционалност „сличну меморији” може пружити само трака. Уместо преписивања тренутног симбола, може обавити инкрементирање модуларном аритметиком над њим. P′′ такође поседује пар инструкција за циклус, испитујући симбол празнине. Упркос својој минималистичкој природи, постао је родитељски формални језик оствареног и (за забаву) кориштеног програмског језика званог Брејнфак.

Као допуна општих рачунских модела, неки једноставнији рачунски модели су корисни за посебне, ограничене примене. Регуларни изрази, на пример, се користе за специфицирање узорака стринга у многим контекстима, од програмске подршке за канцеларијску продуктивност па до програмских језика. Други формализам математички истоветан регуларним изразима, коначни аутомати, се користи у дизајну електронских кругова и при решавању неких проблема. Контекстно независна граматика се користи приликом спецификације синтаксе програмских језика. Недетерминистички потисни аутомати су други формализам истоветан контекстно независним граматикама. Примитивно рекурзивне функције су поткласа рекурзивних функција.

Различити модели рачунања имају способност обављања различитих задатака. Један начин мерења моћи рачунског модела јесте проучавање класе формалних језика које модел може генерисати - ово води ка Чомскијевој хијерархији језика.^[11]

Референце

^ Sipser 2013
^ Hodges 2012
^ Rabin, Michael O. (јун 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. Архивирано из оригинала 05. 06. 2019. г. Приступљено 29. 03. 2019.
^ Monk 1976
^ Alan Turing (1937). „On computable numbers, with an application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society. IEEE. 2 (42): 230—265. doi:10.1112/plms/s2-42.1.230.
^ Rice, Henry Gordon (1953). „Classes of Recursively Enumerable Sets and Their Decision Problems”. Transactions of the American Mathematical Society. American Mathematical Society. 74 (2): 358—366. JSTOR 1990888. doi:10.2307/1990888.
^ Davis 2004
^ <Gödel, Kurt (1931), „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” (PDF), Monatsheft für Math. und Physik, 38: 173—198, Архивирано из оригинала (PDF) 11. 04. 2018. г., Приступљено 29. 03. 2019
^ Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
^ Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the structured program theorem.)
^ Chomsky, Noam (1956). „Three models for the description of language” (PDF). IRE Transactions on Information Theory (2): 113—124. doi:10.1109/TIT.1956.1056813.

Литература

Davis, Martin (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.
Monk, Donald (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701.
Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press. ISBN 978-0-691-15564-7.
Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1. .
Hopcroft, John E.; Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation (3rd изд.). Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9. .
Taylor, R. Gregory (1998). Models of Computation. New York: Oxford University Press.
Hartley Rogers, Jr (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 978-0-262-68052-3. .
Gurari, Eitan (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 978-0-7167-8182-0. Архивирано из оригинала 7. 1. 2007. г.
Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
Linz, P. (2007). An introduction to formal language and automata. Narosa Publishing. ISBN 9788173197819.
Sipser, Michael (2013). Introduction to the Theory of Computation (3rd изд.). Cengage Learning. ISBN 978-1-133-18779-0.
Lewis, F. D. (2007). Essentials of theoretical computer science A textbook covering the topics of formal languages, automata and grammars. The emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the results.
Davis, Martin; Sigal, Ron; Elaine J. Weyuker (1994). Computability, complexity, and languages: fundamentals of theoretical computer science (2nd изд.). Academic Press. ISBN 978-0-12-206382-4. . Covers a wider range of topics than most other introductory books, including program semantics and quantification theory. Aimed at graduate students.
S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. ISBN 978-1-58488-237-4. .
Epstein, Richard L.; Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 978-0-534-54644-1. .
Smith, Carl H. (1994). A recursive introduction to the theory of computation. Springer. ISBN 978-0-387-94332-9. . A shorter textbook suitable for graduate students in Computer Science.

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

„Logika izračunljivosti”. Архивирано из оригинала 11. 04. 2011. г.
-author= -
Theory of Computation at MIT
Theory of Computation at Harvard
„Computability Logic”. - A theory of interactive computation. The main web source on this subject.

[Sipser-3rd-1] Sipser 2013

[Hodges-2012-2] Hodges 2012

[3] Rabin, Michael O. (јун 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. Архивирано из оригинала 05. 06. 2019. г. Приступљено 29. 03. 2019.

[Monk1976-4] Monk 1976

[5] Alan Turing (1937). „On computable numbers, with an application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society. IEEE. 2 (42): 230—265. doi:10.1112/plms/s2-42.1.230.

[6] Rice, Henry Gordon (1953). „Classes of Recursively Enumerable Sets and Their Decision Problems”. Transactions of the American Mathematical Society. American Mathematical Society. 74 (2): 358—366. JSTOR 1990888. doi:10.2307/1990888.

[davis-7] Davis 2004

[8] <Gödel, Kurt (1931), „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” (PDF), Monatsheft für Math. und Physik, 38: 173—198, Архивирано из оригинала (PDF) 11. 04. 2018. г., Приступљено 29. 03. 2019

[bohm1964-9] Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.

[bohm1966-10] Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the structured program theorem.)

[11] Chomsky, Noam (1956). „Three models for the description of language” (PDF). IRE Transactions on Information Theory (2): 113—124. doi:10.1109/TIT.1956.1056813.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]