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



    Podstrony: 1 [2] [3]
    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: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.
    Artystyczna wizja maszyny Turinga

    Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model urządzenia służącego do wykonywania algorytmów. Maszyna składa się z bloku sterowania, głowicy odczytującej i zapisującej oraz nieskończenie długiej taśmy. W każdej komórce taśmy może mieścić się jeden symbol. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z Q stanów. Zależnie od kombinacji stanu maszyny i symbolu napotkanego na taśmie 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. 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.

    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.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.

    Wstęp[ | edytuj kod]

    Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów.

    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).

    Maszyna Turinga A posiadająca zdolność symulacji działania dowolnej innej maszyny Turinga B (opisanej jako dane wejściowe dla maszyny A) na dowolnych danych wejściowych dla maszyny B, nazywana jest uniwersalną maszyną Turinga. Praktycznym przybliżeniem realizacji uniwersalnej maszyny Turinga jest komputer, będący w stanie wykonać dowolny program na dowolnych danych. Jednak komputery nie są uniwersalnymi maszynami Turinga w sensie pierwotnej definicji, ponieważ ilość danych, które mogą przechowywać i przetwarzać jest skończona, tak więc dla każdego komputera istnieje tylko skończona liczba programów, które może wykonać. Mimo że liczba ta jest niewyobrażalnie wielka i w praktyce często wystarczająca, to bez względu na rozmiar pamięci, zawsze będzie istnieć program, którego maszyna nie będzie w stanie wykonać, ponieważ jego kod (opis) po prostu nie mieści się w tej pamięci.

    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:

    Można rozważać bardzo wiele różnych wariantów maszyny Turinga. Na przykład nie ma potrzeby pozwalać na pozostanie maszyny na tym samym polu, ponieważ maszyna musi albo zakończyć obliczenia przez zapętlenie, albo po nie więcej niż N*M krokach dane pole opuścić i wystarczy wtedy przyjąć dla danej kombinacji początkowej stany podczas opuszczania pola.

    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).

    Można rozważać też maszyny Turinga wielotaśmowe lub niedeterministyczne (gdzie jednej parze (symbol, stan) może odpowiadać kilka instrukcji) oraz wielowymiarowe (prostą dwuwymiarową maszyną Turinga jest mrówka Langtona).

    W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Np. dość łatwo jest pokazać, że maszyna Turinga z wieloma taśmami nie różni się istotnie od klasycznej maszyny jednotaśmowej. Również niedeterministyczne maszyny Turinga są równoważne deterministycznym. Rozważania na temat mocy obliczeniowej niedeterministycznych maszyn Turinga są podstawą centralnego problemu teorii złożoności obliczeniowej – „P versus NP”.

    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.

    Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej na przykład niż dowolny komputer), istnieje wiele problemów (np. problem stopu), których nie da się na niej rozwiązać. Matematycy rozważają więc (od czasów samego Turinga) silniejsze modele obliczeń, które mogą takim zadaniom podołać. Hipotetyczne maszyny potrafiące wykonywać takie obliczenia, nazywa się hiperkomputerami. Należy zauważyć, że przy obecnym stanie wiedzy nie jest jasne, czy prawa fizyki rządzące naszym światem pozwalają na skonstruowanie maszyn obliczeniowych silniejszych niż maszyna Turinga. Jest to pole aktywnych prac badawczych.

    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.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.


    Podstrony: 1 [2] [3]




    Warto wiedzieć że... beta

    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.
    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.

    Reklama

    Czas generowania strony: 0.024 sek.