b'\n_START_ARTICLE_\nKompletno\xc5\x9b\xc4\x87 Turinga\n_START_PARAGRAPH_\nKompletno\xc5\x9b\xc4\x87 Turinga \xe2\x80\x93 cecha maszyny lub j\xc4\x99zyka programowania, polegaj\xc4\x85ca na tym, \xc5\xbce mo\xc5\xbcna za jego pomoc\xc4\x85 rozwi\xc4\x85za\xc4\x87 identyczn\xc4\x85 klas\xc4\x99 problem\xc3\xb3w obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyn\xc4\x85 Turinga. W praktyce oznacza to, \xc5\xbce je\xc5\x9bli dany j\xc4\x99zyk lub maszyna potrafi wykona\xc4\x87 lub wyrazi\xc4\x87 ka\xc5\xbcdy algorytm, okre\xc5\x9blany jest mianem zupe\xc5\x82nego, przy czym nie jest wymagane, by algorytm ten realizowany by\xc5\x82 prosto, wydajnie b\xc4\x85d\xc5\xba efektywnie._NEWLINE_Termin wywodzi si\xc4\x99 od nazwiska matematyka Alana Turinga, kt\xc3\xb3ry jako pierwszy zaproponowa\xc5\x82 model uniwersalnej maszyny Turinga.\n_START_SECTION_\nZnaczenie\n_START_PARAGRAPH_\nKompletno\xc5\x9b\xc4\x87 Turinga jest jedn\xc4\x85 z najwa\xc5\xbcniejszych teoretycznych podstaw informatyki. Dzi\xc4\x99ki niej mo\xc5\xbcliwe jest por\xc3\xb3wnywanie mo\xc5\xbcliwo\xc5\x9bci r\xc3\xb3\xc5\xbcnych projekt\xc3\xb3w maszyn obliczeniowych. Je\xc5\xbceli na zaproponowanym modelu obliczeniowym da si\xc4\x99 zasymulowa\xc4\x87 uniwersaln\xc4\x85 maszyn\xc4\x99 Turinga, oznacza to, \xc5\xbce jest on w stanie rozwi\xc4\x85za\xc4\x87 tak\xc4\x85 sam\xc4\x85 ilo\xc5\x9b\xc4\x87 problem\xc3\xb3w algorytmicznych, jak inne modele. Pr\xc3\xb3ba implementacji maszyny Turinga na takim modelu jest te\xc5\xbc jednocze\xc5\x9bnie dowodem jego kompletno\xc5\x9bci. Kompletno\xc5\x9b\xc4\x87 Turinga wynika z niemo\xc5\xbcliwej do udowodnienia hipotezy Churcha-Turinga._NEWLINE_Maszyna Turinga jest modelem wyidealizowanym, niemo\xc5\xbcliwym do skonstruowania ze wzgl\xc4\x99du na konieczno\xc5\x9b\xc4\x87 posiadania niesko\xc5\x84czonej pami\xc4\x99ci. Ograniczenie zasob\xc3\xb3w cechuje wszystkie istniej\xc4\x85ce obecnie komputery, dlatego terminu kompletno\xc5\x9b\xc4\x87 Turinga u\xc5\xbcywa si\xc4\x99 w odniesieniu do nich w znaczeniu, \xc5\xbce by\xc5\x82yby one kompletne, gdyby posiada\xc5\x82y nielimitowan\xc4\x85 ilo\xc5\x9b\xc4\x87 zasob\xc3\xb3w. Zgodnie z tym rozumowaniem, wszystkie obecne komputery s\xc4\x85 zupe\xc5\x82ne w sensie Turinga \xe2\x80\x93 jest tak, poniewa\xc5\xbc j\xc4\x99zyki niskiego poziomu, kt\xc3\xb3rymi pos\xc5\x82uguj\xc4\x85 si\xc4\x99 procesory s\xc4\x85 zupe\xc5\x82ne. Istniej\xc4\x85 natomiast \xe2\x80\x93 i to te\xc5\xbc jest oczywiste \xe2\x80\x93 j\xc4\x99zyki programowania, kt\xc3\xb3re nie s\xc4\x85 zupe\xc5\x82ne w sense Turinga, przyk\xc5\x82adem jest j\xc4\x99zyk SQL._NEWLINE_Pierwszym projektem komputera zupe\xc5\x82nego w sensie Turinga by\xc5\x82a maszyna analityczna zaproponowana w 1837 roku przez angielskiego matematyka Charlesa Babbage\xe2\x80\x99a, lecz nigdy nie zosta\xc5\x82a ona zbudowana. Do niedawna uwa\xc5\xbcano, \xc5\xbce pierwszym dzia\xc5\x82aj\xc4\x85cym zupe\xc5\x82nym komputerem by\xc5\x82 ameryka\xc5\x84ski ENIAC uruchomiony w 1944, jednak w 1998 roku Ra\xc3\xbal Rojas udowodni\xc5\x82 kompletno\xc5\x9b\xc4\x87 niemieckiego komputera Z3, zbudowanego i uruchomionego w 1941 roku w Berlinie przez Konrada Zuse._NEWLINE_Przerwa mi\xc4\x99dzy rokiem 1837 a 1941 nie by\xc5\x82a czasem systematycznego rozwoju mechanicznego komputera. Znacz\xc4\x85cy rozw\xc3\xb3j komputer\xc3\xb3w nast\xc4\x85pi\xc5\x82 dopiero po opracowaniu we wczesnych latach 30. XX wieku matematycznych sposob\xc3\xb3w wyra\xc5\xbcania problem\xc3\xb3w obliczeniowych oraz pierwszych j\xc4\x99zyk\xc3\xb3w formalnych._NEWLINE_Istnieje hipoteza m\xc3\xb3wi\xc4\x85ca, \xc5\xbce ca\xc5\x82y wszech\xc5\x9bwiat jest zupe\xc5\x82ny w sensie Turinga. Oznacza\xc5\x82oby to, \xc5\xbce niemo\xc5\xbcliwe jest zbudowanie maszyny pot\xc4\x99\xc5\xbcniejszej, ni\xc5\xbc uniwersalna maszyna Turinga oraz podobne do niej. Zobacz artyku\xc5\x82 Teoria obliczalno\xc5\x9bci, aby znale\xc5\xba\xc4\x87 list\xc4\x99 modeli zupe\xc5\x82nych w sensie Turinga, modeli o mniejszych mo\xc5\xbcliwo\xc5\x9bciach oraz teoretycznych, znacznie pot\xc4\x99\xc5\xbcniejszych modeli.\n_START_SECTION_\nPowi\xc4\x85zane zagadnienia\n_START_PARAGRAPH_\nWa\xc5\xbcnym wnioskiem p\xc5\x82yn\xc4\x85cym z teorii obliczalno\xc5\x9bci jest niemo\xc5\xbcliwo\xc5\x9b\xc4\x87 okre\xc5\x9blenia w og\xc3\xb3lnym przypadku, czy dany program zatrzyma si\xc4\x99 dla wszystkich mo\xc5\xbcliwych danych, czy te\xc5\xbc b\xc4\x99dzie wykonywa\xc4\x87 si\xc4\x99 w niesko\xc5\x84czono\xc5\x9b\xc4\x87 (tzw. problem stopu). Jedn\xc4\x85 z powszechnych metod radzenia sobie z problemem jest wymuszenie zatrzymania si\xc4\x99 po okre\xc5\x9blonym czasie lub ograniczenie mocy instrukcji przep\xc5\x82ywu sterowania w programie, jednak takie systemy nie s\xc4\x85 zupe\xc5\x82ne w sensie Turinga._NEWLINE_Kolejnym interesuj\xc4\x85cym zagadnieniem zwi\xc4\x85zanym z kompletno\xc5\x9bci\xc4\x85 jest fakt, \xc5\xbce istniej\xc4\x85 problemy rozwi\xc4\x85zywalne w j\xc4\x99zykach zupe\xc5\x82nych, a kt\xc3\xb3re nie maj\xc4\x85 rozwi\xc4\x85zania w j\xc4\x99zykach udost\xc4\x99pniaj\xc4\x85cych jedynie sko\xc5\x84czone p\xc4\x99tle, tzn. gwarantuj\xc4\x85cych, \xc5\xbce program si\xc4\x99 zatrzyma.'