Turing-ukoczony



Informacje, które udało nam się zgromadzić na temat Turing-ukoczony , zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Turing-ukoczony . W Internecie łatwo zgubić się w gąszczu stron, które mówią o Turing-ukoczony , a jednocześnie nie podają tego, co chcemy wiedzieć o Turing-ukoczony . Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Turing-ukoczony poniżej. Jeśli informacje o Turing-ukoczony , które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.

.

W informatyce oraz w logice , wykorzystujc system formalny jest uwaane za kompletny w sensie Turinga lub Turing-complete (przez warstwy angielskiej Turinga kompletne ), jeli to ma si wyrazu co najmniej równowany z tym, maszyn Turinga . W takim systemie moliwe jest zatem zaprogramowanie dowolnej maszyny Turinga.

Pojcie to nadaje sens tezie Kocioa , która postuluje istnienie naturalnego pojcia obliczalnoci. Tak wic sia wyrazu maszyn Turinga zbiega si z si funkcji rekurencyjnych , rachunku lambda , a nawet maszyn liczcych .

Chocia niektóre modele oblicze, zwane hiperkomputerami , s cilej bardziej wyraziste ni maszyny Turinga, modele te s przedmiotem spekulacji (wymagajcych np. wykonania nieskoczonej liczby operacji lub obliczenia na zbiorze liczb rzeczywistych) i nie jest wiadomo, czy s one fizycznie wykonalne. W tych warunkach teza Churcha zakada powszechno modelu obliczeniowego maszyny Turinga: kady kompletny system Turinga byby w rzeczywistoci równowany maszynom Turinga.

Jzyki programowania Turing-complete

Podobnie jak model obliczeniowy, o jzyku komputerowym mówi si, e jest kompletny pod wzgldem Turinga, jeli pozwala na reprezentacj wszystkich funkcji obliczeniowych w sensie Turinga i Churcha (pomimo skoczonoci pamici komputera).

Niektórzy autorzy przyjmuj t waciwo do definicji jzyka programowania , ale mona wybra inne definicje.

Zwyke jzyki programowania ( C , Java ) s Turing-kompletne, poniewa zawieraj wszystkie skadniki niezbdne do symulacji uniwersalnej maszyny Turinga (liczenie, porównywanie, odczytywanie, pisanie itp.). Jzyk C++ jest równie kompletny pod wzgldem Turinga, a podzbiór umoliwiajcy programowanie generyczne ( szablony ) jest równie [ref. konieczne] .

Jzyk SQL , pierwotnie niekompletny w sensie Turinga, sta si nim wraz ze standardem SQL: 1999 umoliwiajcym pisanie zapyta rekurencyjnych [ref. konieczne] .

Jzyk LaTeX (od TeX ), przeznaczony do komponowania dokumentów, jest równie Turing-complete.

Sam jzyk HTML nie jest Turing-kompletny, jednak udowodniono, e jzyk CSS (w wersji 3) pozwala zbudowa elementarny automat komórkowy kodu 110 (patrz Regua 110  (en) ), znany jako uniwersalny. poczucie Turinga. Te dwa jzyki s czsto nierozczne, moemy wywnioskowa, e HTML + CSS jest Turing-complete, a wic to skojarzenie teoretycznie czyni z niego jzyk programowania.

Jzyk z kompletem Turinga dziedziczy cechy maszyny Turinga. Na przykad problem z zamkniciem jest nierozstrzygnity , wic nie mona napisa programu, który mówi, czy dany mu dowolny program si koczy, czy nie.

Jzyki, które nie s kompletne pod wzgldem Turinga

Niektóre jzyki przeznaczone do rozwizywania konkretnych problemów nie s kompletne pod wzgldem Turinga. Przykadem jest System F , formalizm rachunku lambda. Co wicej - z zaoenia - jzyki totalne  (en) , w których wszystkie obliczenia koniecznie si kocz (jak jzyk Gallina asystenta dowodu Coq ), równie nie s Turinga-zupene. Jednak ci ostatni w praktyce s w stanie obliczy wszystko, co jest interesujce, innymi sowy mog realizowa wszystkie funkcje, których moemy potrzebowa w yciu praktycznym; obliczenia, które im wymykaj si, albo maj zoono wykraczajc poza to, co mona sobie wyobrazi i zrealizowa, albo nie kocz si. Kompilacja musi nastpnie zademonstrowa zakoczenie programów lub wymaga interakcji z programist w przypadku niektórych demonstracji, ale jest to cena za jako kodu, która jest poprawna z punktu widzenia konstrukcji.

Przykady poza jzykami programowania

Niektóre gry i oprogramowanie s kompletne pod wzgldem Turinga przez przypadek, a ich autorzy nie chc tego ani nie bior pod uwag:

Powizane artykuy

Uwagi i referencje

Uwagi

  1. Komputer ma skoczon pami, model maszyny Turinga ma nieograniczon pami.

Bibliografia

  1. Biuro Tumacze , rekord bazy danych TERMIUM Plus , na termiumplus.gc.ca ,(dostp 23 maja 2019 )
  2. (w) John C. Mitchell, Concepts in Programming Languages , Cambridge University Press ,( czytaj online ) , s.  14 :

    Fakt, e wszystkie standardowe jzyki programowania dokadnie wyraaj klas czciowych funkcji rekurencyjnych, czsto podsumowuje stwierdzenie, e wszystkie jzyki programowania s kompletne wedug Turinga.  "

  3. (w) Bruce J. MacLennan, Principles of Programming Languages , Oxford University Press ,, Wprowadzenie: Co to jest jzyk programowania :

      Jzyk programowania to jzyk przeznaczony do wyraania programów komputerowych i zdolny do wyraania dowolnego programu komputerowego. To nie jest mgliste pojcie. Istnieje precyzyjny teoretyczny sposób okrelenia, czy jzyk komputerowy moe by uyty do wyraenia dowolnego programu, a mianowicie poprzez wykazanie, e jest on odpowiednikiem uniwersalnej maszyny Turinga.  "

  4. (w) Czy jzyki uzupenione Turingiem w ogóle nie s uznawane za jzyki programowania  » , Na giedzie stosów
    Na zadane pytanie wybrana odpowied uwaa, e kompletno Turinga nie jest wymagana, aby uzna jzyk za jzyk programowania.
  5. Przykad implementacji Maszyny Turinga w C: (en) Juan Pablo Rinaldi (juampi),   Wdroenie Maszyny Turinga w C   , na GitHub ,(dostp 21 maja 2019 r . ) .
  6.   LaTeX jest potniejszy ni mylisz obliczanie liczb Fibonacciego i kompletno Turinga ShareLaTeX, internetowy edytor LaTeX   na stronie fr.sharelatex.com (dostp 2 czerwca 2017 r . ) .
  7. (w) Eli & Jonas,   Udowodniono, e CSS3 jest Turing complete   na Accodeing to you (dostp 17 maja 2019 r . ) .
  8.   O znaczeniu zupenoci Turinga   o Lambdzie Ostatecznej  (w) .
  9. Benjamin Werner,   Zestawy w rodzajach , rodzaje w zestawach  , Procedury TACS'97 ,.
  10. Czowiek uywa najtrudniejszej gry komputerowej na wiecie do stworzenia dziaajcej maszyny Turinga (wersja archiwum internetowego z 27 czerwca 2015 r. ) , na stronie www.themarysue.com ,.
  11. Paul Rendell , Maszyna Turinga w grze Conway's Game of Life (wersja archiwum internetowego z 8 lipca 2009 r. ) , pod adresem rendell-attic.org ,.
  12. (w) Alex Churchill , Magic: The Gathering is Turing completeness (wersja z 7 maja 2019 r. w Internet Archive ) z Cornell University ,.
  13. (w) Gunivers,   Data Pack Universal Turing Machine   , na YouTube ,(dostp 6 maja 2020 r . ) .
  14. (w) Tom Wildenhain,   O Turing Completeness of MS PowerPoint   na https://www.andrew.cmu.edu/user/twildenh/ ,(dostp 10 lipca 2020 r. )
  15. (w) Habbo (@Habbo), Wiemy, e s utalentowani Niektórzy Habbo d do tego, e ten moe po prostu zabra ciasto! Jeden z naszych graczy @sirjonasxx podj wyzwanie stworzenia dziaajcej maszyny Turinga w grze i UDAO SI! Sprawdmy to.  » , na Twitterze ,(dostp 30 listopada 2020 r. )

Zaczniki

Powizane artykuy

Mamy nadzieję, że informacje, które zgromadziliśmy na temat Turing-ukoczony , były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Turing-ukoczony i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Turing-ukoczony na tej stronie pomogło Ci poszerzyć swoją wiedzę.

Opiniones de nuestros usuarios

Darek Borkowski

Byłem zachwycony, że znalazłem ten artykuł na temat _zmienna.

Bart Konieczny

Dzięki. Pomógł mi artykuł o Turing-ukoczony .