• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Maszyna Turinga



    Podstrony: [1] 2 [3] [4]
    Przeczytaj także...
    Encyklopedia PWN – encyklopedia internetowa, oferowana – bezpłatnie i bez konieczności uprzedniej rejestracji – przez Wydawnictwo Naukowe PWN. Encyklopedia zawiera około 122 tysiące haseł i 5 tysięcy ilustracji.Symbol (z gr. σύμβολον) – semantyczny środek stylistyczny, który ma jedno znaczenie dosłowne i nieskończoną liczbę znaczeń ukrytych. Odpowiednik pojęcia postrzegany zmysłowo. Najbardziej ogólnie jest to zastąpienie jednego pojęcia innym, krótszym, bardziej wyrazistym lub najlepiej oddającym jego naturę, albo mniej abstrakcyjnym. Jest to znak odnoszący się do innego systemu znaczeń, niż do tego, do którego bezpośrednio się odnosi. Przykładowo symbol lwa oznacza nie tylko dany gatunek zwierzęcia, lecz często także siłę lub władzę. Symbole są pewnymi znakami umownymi, które w różnych kulturach mogą mieć różne znaczenia - to odróżnia symbol od jednoznacznej alegorii. Znaczenia szczególne to między innymi:
    Zapis formalny[ | edytuj kod]
    Grafika przedstawiająca maszynę Turinga w stanie q1 nad zerem na taśmie

    Formalnie maszynę Turinga opisuje się poprzez krotkę:

    gdzie:

    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.
    – skończony zbiór stanów stan początkowy, – zbiór stanów końcowych – skończony zbiór dopuszczalnych symboli symbol pusty, – zbiór symboli wejściowych – podzbiór zbioru do którego nie należy funkcja opisana następująco: co oznacza, że jest to funkcja pobierająca aktualny stan maszyny oraz symbol wejściowy, a dającą w wyniku symbol, jaki ma się pojawić na taśmie, kolejny stan maszyny oraz przesunięcie głowicy maszyny (lewo, prawo lub bez przesunięcia).

    Inne ujęcie[ | edytuj kod]

    Model przedstawiony przez Rogera Penrose’a w Nowym umyśle cesarza (s. 46–93, ​ISBN 83-01-11819-9​) jest nieco inny, bardziej oszczędny, chociaż równoważny matematycznie.

    Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.Rachunek lambda – system formalny używany do badania zagadnień związanych z podstawami matematyki jak rekurencja, definiowalność funkcji, obliczalność, podstawy matematyki np. definicja liczb naturalnych, wartości logicznych itd. Rachunek lambda został wprowadzony przez Alonzo Churcha i Stephena Cole’a Kleene’ego w 1930 roku.

    Przyjmuje się, że maszyna obsługuje tylko dwa znaki na taśmie – zero i jedynkę. Przy tym stany wewnętrzne są oznaczone liczbami dwójkowymi i maszyna zaczyna od stanu 0. Maszyna po każdej operacji zmienia stan wewnętrzny, znak na taśmie i przesuwa się w lewo lub w prawo. Może też się zatrzymać. Reguły oznacza się przez odpowiedni zestaw przejść, np. (ostatnia cyfra oznacza znak na taśmie i jest wytłuszczona dla czytelności)

    Komputer (z ang. computer od łac. computare – liczyć, sumować; dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – maszyna elektroniczna przeznaczona do przetwarzania informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego.Stanford Encyclopedia of Philosophy (SEP) jest ogólnie dostępną encyklopedią internetową filozofii opracowaną przez Stanford University. Każde hasło jest opracowane przez eksperta z danej dziedziny. Są wśród nich profesorzy z 65 ośrodków akademickich z całego świata. Autorzy zgodzili się na publikację on-line, ale zachowali prawa autorskie do poszczególnych artykułów. SEP ma 1260 haseł (stan na 20 stycznia 2011). Mimo, że jest to encyklopedia internetowa, zachowano standardy typowe dla tradycyjnych akademickich opracowań, aby zapewnić jakość publikacji (autorzy-specjaliści, recenzje wewnętrzne).
    00 → 00R,
    01 → 11R,
    10 → 01R.STOP,
    11 → 11R.
    

    Jest to maszyna UN+1 zwiększająca liczbę zapisaną w systemie jedynkowym o jeden, czyli dopisująca na końcu pierwszego ciągu jedynek na taśmie jeszcze jedną jedynkę.

    Można przyjąć, że instrukcja L.STOP nigdy nie występuje, gdyż odpowiedź ma znaleźć się po lewej stronie maszyny. Dlatego R.STOP skraca się do STOP. W ten sposób zapisuje się maszynę UN×2 jako

    00 → 00R,
    01 → 10R,
    10 → 101L,
    11 → 11R,
    100 → 110R,
    101 → 1000R,
    110 → 01STOP,
    111 → 111R,
    1000 → 1011L,
    1001 → 1001R,
    1010 → 101L,
    1011 → 1011L.
    

    Opis maszyny EUC, znajdującej największy wspólny dzielnik dwóch liczb naturalnych zawiera 22 instrukcje dotyczące 11 stanów wewnętrznych (tylko 3 z tych instrukcji powodują zmianą zapisu na taśmie). Przekształca ona na przykład ciąg

    Maszyna RAM - w informatyce model abstrakcyjnej maszyny będący odmianą maszyny rejestrowej, bardzo podobnej do maszyny licznikowej, lecz z możliwością niebezpośredniego adresowania jej rejestrów. Model RAM wykorzystywany jest podczas analizy złożoności obliczeniowej algorytmów.Automat Büchiego (ang. Büchi automaton) to rozszerzenie automatu skończonego na słowa nieskończone. Automat Büchiego składa się z:
    ...000111111011111111000...

    w ciąg ...00011000...

    (Największy wspólny dzielnik liczb 6 i 8 to 2.)

    Większą liczbę znaków można zastąpić rozszerzoną notacją dwójkową. Na przykład 0 może oznaczać 0, 101, a 1102 itp. Jeżeli 2 oznacza przecinek, ciąg liczb dwójkowych 101, 1101, 0, 1, 1, 100,

    zapisuje się, stosując ekspansję jako

    Alan Mathison Turing (ur. 23 czerwca 1912 w Londynie, zm. 7 czerwca 1954 w Wilmslow) – angielski matematyk, kryptolog, twórca pojęcia maszyny Turinga i jeden z twórców informatyki.MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).
    ...000100101101010010110011010110101101000110000...

    W rozszerzonej notacji dwójkowej można zakodować też symbol oznaczający koniec wyniku, ale dla uproszczenia można np. przyjąć, że maszyna oznacza jakoś pola, które przez nią przeszły i nie trzeba sprawdzać całej taśmy, aby przekonać się, że w dalszej części zawiera same zera.

    Otwarty dostęp (OD, ang. Open Access, „OA”) – oznacza wolny, powszechny, trwały i natychmiastowy dostęp dla każdego do cyfrowych form zapisu danych i treści naukowych oraz edukacyjnych.Nationalencyklopedin – największa, szwedzka encyklopedia współczesna. Jej stworzenie było możliwe dzięki kredytowi w wysokości 17 mln koron, którego udzielił rząd szwedzki w 1980 roku i który został spłacony w 1990. Drukowana wersja składa się z 20 tomów i zawiera 172 tys. haseł. Wersja internetowa zawiera 260 tys. haseł (stan z czerwca 2005). Inicjatorem projektu był rząd szwedzki, który rozpoczął negocjacje z różnymi wydawcami. Negocjacje zakończyły się w 1985, kiedy na wydawcę został wybrany Bra Böcker z Höganäs. Encyklopedia miała uwzględniać kwestie genderowe i związane z ochroną środowiska. Pierwszy tom ukazał się w 1989 roku, ostatni w 1996. Dodatkowo w roku 2000 ukazały się trzy dodatkowe tomy. Encyklopedię zamówiło 54 tys. osób. W 1997 roku ukazało się wydanie elektroniczne na CD, a w 2000 pojawiło się wydanie internetowe, które jest uzupełniane na bieżąco.

    Maszyny wykorzystujące taki kod są zwykle bardziej skomplikowane, ale szybsze. Np. maszyna XN+1 zwiększająca liczbę zapisaną w systemie dwójkowym za pomocą rozszerzonej notacji dwójkowej o 1:

    00 → 00R,
    01 → 11R,
    10 → 00R,
    11 → 101R,
    100 → 110L,
    101 → 101R,
    110 → 01STOP,
    111 → 1000L,
    1000 → 1011L,
    1001 → 1001R,
    1010 → 1100R,
    1011 → 101R,
    1101 → 1111R,
    1110 → 111R,
    1111 → 1110R.
    

    Maszyna XN×2 mnożąca przez dwa jest jednak prostsza od UN×2:

    00 → 00R,
    01 → 11R,
    10 → 00R,
    11 → 100R,
    100 → 111R,
    110 → 00STOP.
    

    Opis maszyny Turinga można zakodować, oznaczając 0, 1, R, L, STOP, strzałkę i przecinek przez liczby od 0 do 6, czyli 0, 10, 110, 1110, 11110, 111110, 1111110. Jednak przecinek jest zbędny (wystarczy samo R, L lub STOP), tak jak stany wejściowe (o ile dane są podane po kolei, np. w XN+1 należy dodać np. 101 → 00R). Wtedy otrzymamy 0 i 00, 1 i 110, R → 110, L → 1110 oraz STOP → 11110. Maszyna XN+1 jest teraz opisana przez

    Program komputerowy (ang. computer program) - sekwencja symboli opisująca obliczenia zgodnie z pewnymi regułami zwanymi językiem programowania. Program jest zazwyczaj wykonywany przez komputer (np. wyświetlenie strony internetowej), czasami bezpośrednio – jeśli wyrażony jest w języku zrozumiałym dla danej maszyny lub pośrednio – gdy jest interpretowany przez inny program (interpreter). Program może być ciągiem instrukcji opisujących modyfikacje stanu maszyny ale może również opisywać obliczenia w inny sposób (np. rachunek lambda).Library of Congress Control Number (LCCN) – numer nadawany elementom skatalogowanym przez Bibliotekę Kongresu wykorzystywany przez amerykańskie biblioteki do wyszukiwania rekordów bibliograficznych w bazach danych i zamawiania kart katalogowych w Bibliotece Kongresu lub u innych komercyjnych dostawców.
    00R 11R 00R 101R 110L 101R 01STOP 1000L 1011L 1001L 1100R 101R 00R 1111R 111R 1110R

    Pomijając początkowe (00R to początek każdej maszyny Turinga) i końcowe (każdy opis kończy się symbolem R, L lub STOP), 110 zapisuje się 10101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100

    czyli dziesiętnie 450 813 704 461 563 958 982 113 775 643 437 908

    Z kolei numer dwójkowy UN+1 to

    Dwójkowy system liczbowy, system binarny, bin – pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1.Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.
    101011010111101010

    czyli dziesiętnie 177 642.

    XN×2 ma numer 1 456 581 339, a UN×2 – 1 492 923 420 919 872 026 917 547 669.

    Pierwsze trzynaście maszyn:

    T0: 00 → 00R, 01 → 00R,
    T1: 00 → 00R, 01 → 00L,
    T2: 00 → 00R, 01 → 01R,
    T3: 00 → 00R, 01 → 00STOP,
    T4: 00 → 00R, 01 → 10R,
    T5: 00 → 00R, 01 → 01L,
    T6: 00 → 00R, 01 → 00R, 10 → 00R,
    T7: 00 → 00R, 01 →???,
    T8: 00 → 00R, 01 → 100R,
    T9: 00 → 00R, 01 → 10L,
    T10: 00 → 00R, 01 → 11R,
    T11: 00 → 00R, 01 → 01STOP,
    T12: 00 → 00R, 01 → 00R, 10 → 00R
    

    Większość jest niekompletna (bywa na przykład, że zawierają więcej, niż cztery jedynki z rzędu, czyli są niepoprawnie określone) lub nigdy się nie zatrzymuje, zdarzają się też powtórzenia. Żaden system kodowania nie pozwala wyeliminować wszystkich takich dat.

    Sir Roger Penrose (ur. 8 sierpnia 1931 w Colchester w Anglii) – angielski fizyk i matematyk. Jest synem lekarza, genetyka i matematyka Lionela Penrose’a oraz bratem matematyka Olivera Penrose’a i szachisty Jonathana Penrose’a.I Liceum Ogólnokształcące im. Kazimierza Brodzińskiego – jedna ze szkół ponadgimnazjalnych w Tarnowie. Mieści się przy ulicy Piłsudskiego 4. Od 2013 dyrektorem szkoły jest polonistka mgr Jadwiga Skolmowska. Szkoła nosi imię absolwenta szkoły, powszechnie uważanego za najwybitniejszego twórcę preromantyzmu w Polsce, Kazimierza Brodzińskiego. W 2009 obchodziła jubileusz 450-lecia istnienia.

    Pewna skomplikowana maszyna Turinga zastosowana do numeru dowolnej maszyny Turinga i jej argumentu da wynik działania tej maszyny.

    Podstrony: [1] 2 [3] [4]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Funkcja rekurencyjna – funkcja N i → N {displaystyle mathbb {N} ^{i} ightarrow mathbb {N} } , która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:
    Biblioteka Narodowa Francji (fr. Bibliothèque nationale de France, BnF) – francuska biblioteka narodowa, znajdująca się w Paryżu. Przewidziana jest jako repozytorium dla wszystkich materiałów bibliotecznych, wydawanych we Francji. Obecnym dyrektorem Biblioteki jest Bruno Racine.
    Zbiór – pojęcie pierwotne teorii zbiorów (znanej szerzej jako teoria mnogości; za jej twórcę uważa się Georga Cantora) leżące u podstaw całej matematyki; intuicyjnie jest to nieuporządkowany zestaw różnych obiektów, czy też kolekcja niepowtarzających się komponentów bez wyróżnionej kolejności.
    Funkcja (łac. functio, -onis, „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.
    Krotka (ang. tuple) - struktura danych będąca odzwierciedleniem matematycznej n-ki, tj. uporządkowanego ciągu wartości. Krotki przechowują stałe wartości o różnych typach danych - nie można zmodyfikować żadnego elementu, odczyt natomiast wymaga podania indeksu liczbowego żądanego elementu.
    Hiperkomputer – hipotetyczna maszyna obliczeniowa (komputer) dysponująca większą mocą obliczeniową niż maszyna Turinga, tzn. taka, która potrafi wykonywać algorytmy, których nie jest w stanie wykonać maszyna Turinga. Mówimy, że potrafią one wykonywać hiperobliczenia, w odróżnieniu od "zwykłych" obliczeń, które wykonują maszyny Turinga.
    Problem stopu – zagadnienie algorytmiczne odpowiadające dla danego algorytmu na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu.

    Reklama

    Czas generowania strony: 0.036 sek.