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



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    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:Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) – system reprezentacji liczb całkowitych w dwójkowym systemie pozycyjnym. Jest obecnie najpopularniejszym sposobem zapisu liczb całkowitych w systemach cyfrowych. Jego popularność wynika z faktu, że operacje dodawania i odejmowania są w nim wykonywane tak samo jak dla liczb binarnych bez znaku. Z tego też powodu oszczędza się na kodach rozkazów procesora.
    Artystyczna wizja maszyny Turinga
    Grafika przedstawiająca maszynę Turinga w stanie q1 nad zerem na taśmie

    Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model komputera służącego do wykonywania algorytmów, składającego się z nieskończenie długiej taśmy podzielonej na pola w których zapisuje się dane. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.

    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.

    Spis treści

  • 1 Wstęp
  • 2 Zapis formalny
  • 3 Przykłady maszyny Turinga
  • 3.1 Podwajanie znaków
  • 3.2 Sprawdzanie palindromów
  • 3.2.1 Działanie dla ΦabaΦ
  • 3.2.2 Działanie dla ΦabbΦ
  • 3.3 Negowanie w kodzie U2
  • 4 Inne ujęcie
  • 5 Zobacz też
  • 6 Linki zewnętrzne


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



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

    Warto wiedzieć że... beta

    Palindrom (gr. palindromeo – biec z powrotem) – wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.
    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.
    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:
    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).
    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).

    Reklama

    Czas generowania strony: 0.022 sek.