Komentarze (52)

  • kidzior +21  

    Studenci studiów informatycznych muszą mieć opanowaną zasadę działania tej zmyślnej maszyny. Podobnie jak zasadę liczenia maszyny von Neumana. ;-)

    http://en.wikipedia.org/wiki/Turing_machine

    pokaż komentarz
    kidzior
  • anath0r +16  

    tak

    pokaż komentarz
    anath0r
  • RobusCracker +25  

    nie

    pokaż komentarz
    RobusCracker
  • Krfk +78  

    lubię placki

    pokaż komentarz
    Krfk
  • Reklamy Google

  • k.....b +2  

    Polecam sobie poczytac co nieco o samym Turingu.

    http://pl.wikipedia.org/wiki/Alan_Mathison_Turing

    pokaż komentarz
    k.....b
  • m.....i +42  

    @kidzior:
    Polska Wikipedia istnieje od dość dawna i ma się dobrze:
    http://pl.wikipedia.org/wiki/Maszyna_Turinga

    pokaż komentarz
    m.....i
  • mrowek +3  

    @milordi - ale wiele haseł ma mniej treści niż w angielskiej wersji ;]

    pokaż komentarz
    mrowek
  • baby-face -7  

    Lubię placki albo nie lubię placków, zależy to od tego w jakim stanie akurat się znajduje. Czasem zjadam je do połowy i mi się odechciewa a czasami plackami rzygam.
    Kwantowa maszyna Turinga to dopiero coś ;)

    pokaż komentarz
    baby-face
  • kidzior -3  

    @milordi: Maszyna lepiej opisana jest na anglojęzycznej Wiki.

    pokaż komentarz
    kidzior
  • w.......s +13  

    Ja bym był wdzięczny gdyby ktoś w miarę opisał, o co chodzi. Bo opis na wikipedii jest zbyt precyzyjny. :)

    pokaż komentarz
    w.......s
  • kowad +1  

    Maszyna która potrafi czytać z taśmy i zapisywać na taśmie jakieś określone znaki.
    Zastosowań takiej maszyny jest bardzo wiele.
    Więcej o samej maszynie: http://www.eioba.pl/a1921/maszyna_turinga
    a tutaj: http://www.mimuw.edu.pl/~kubica/aug/frames-jfa-main-node16.html przykład (musisz zjechać trochę w dół) wykorzystania maszyny do sprawdzenia czy dany ciąg znaków to: a powtórzone n razy, b powtórzone n razy, c powtórzone n razy.

    pokaż komentarz
    kowad
  • c....o +17  

    No więc te klocki które maszyna "czyta" i przesuwa to są zera i jedynki. Jest to model działania obecnych komputerów. W dużym uproszczeniu mówiąc, gdybyś miał długą prowadnicę po której przesuwa się ta mszynka (głowica) i mniej więcej, tyle na niej klocków ułożonych, co tranzystorów w Twoim kompie, to maszyna ta potrafiła by zrobić dokładnie wszystko to co Twój komputer, tylko ze względu na szybkość działania, nie dożyłbyś np. generowania jednej klatki w Twojej ulubionej gry 3D ;p

    pokaż komentarz
    c....o
  • Neratin +6  

    Chodzi o to, że to po pierwsze żadna maszyna, a po drugie zastosowań praktycznych nie ma żadnych. Jest to formalizm matematyczny, który posłużył Turingowi do pokazania, co da się zrobić przy pomocy "komputera" (tzn. algorytmicznie), a przede wszystkim czego się nie da zrobić.

    Dowcip polega więc na tym, że ktoś odwzorował z klocków lego pewną matematyczną abstrakcję w dosłowny sposób.

    Mniej dosłowny jest tutaj:

    http://www.monochrom.at/turingtrainterminal/pictures_eng.htm

    pokaż komentarz
    Neratin
  • s..........y 0  

    W uproszczeniu Maszyna Turinga to taki pierwowzór komputera, który składa się z nieskończonej taśmy (pamięć) i automatu stanowego (program). Maszyna została wymyślona do celów teoretycznych np. żeby udowodnić pewne twierdzenia z teorii obliczeń.

    pokaż komentarz
    s..........y
  • Sh1eldeR +38  

    [gdy usiłowałem napisać komentarz z łopatologicznym opisem, parę osób mnie ubiegło... dodam go i tak -- może komuś się przyda]

    Można powiedzieć, że to najprostszy model komputera. I to taki, na którym da się wykonać praktycznie dowolny algorytm, który da się wykonać na normalnym komputerze. Teoretycznie więc mógłbyś zainstalować na tym Linuksa, cokolwiek by to w tym wypadku oznaczało.

    A co do sposobu działania... Maszyna składa się z podzielonej na pola taśmy (każde pole zawiera jakąś daną, np. 1 lub 0) oraz głowicy odczytująco/zapisującej. Taśma powinna mieć nieskończoną długość ;), a głowica nad nią może się przesuwać. Aha, oprócz tego maszyna posiada wewnętrzny stan, który może się zmienić po odczytaniu/zapisaniu czegoś na taśmie.

    I tyle. Pomyśleć, że taka maszyna potrafi rozwiązać (niemal) każdy problem (niemal, bo nie wszystkie są rozwiązywalne).

    Jak to działa? Najpierw musimy napisać program, bo bez tego maszyna Turinga tylko sobie leży na biurku ;) i nic nie robi. Jak taki program wygląda?To tzw. funkcja przejść. To bardzo proste: mówimy w niej, że gdy maszyna jest w jakimś stanie i napotka na taśmie jakiś symbol, to ma zmienić stan na inny (lub nie), ewentualnie zapisać nową wartość symbolu i przesunąć w lewo lub w prawo.

    Na przykład:
    Jeśli maszyna jest w stanie GRA-ZAPAUZOWANA i odczyta z taśmy "1" -- to ma zmienić stan na GRA-W-TOKU, zapisać w to miejsce na taśmie "0" i przesunąć głowicę w prawo.

    Takich przejść definiuje się całe mnóstwo i powstają np. szachy ;-) (no dobra, komu by się chciało napisać w ten sposób szachy?)

    A z realniejszych zadań, jakie może wykonać maszyna? Np. sortowanie dowolnie dużych liczb. Nawet jeśli w poszczególnych polach na taśmie nie mogą występować całe liczby, a tylko cyfry "1" lub "0", to możemy użyć zapisu binarnego (zamiast 0, 1, 2, 3, 4, 5... - 0, 1, 10, 11, 100, 101...), albo -- co zwykle jest szczególnie wygodne, o ile można to tak nazwać -- systemu jedynkowego. Czyli liczby składają się z samych jedynek, a oddzielone są zerami. Np. 1 zapisujemy "1", a 5 zapisujemy jako "11111" (5 jedynek).

    Piszemy (ździebko skomplikowaną) funkcję przejść i nasza maszyna dostając na taśmie ciąg:

    111011111010101100

    (to zakodowane systemem jedynkowym, rozdzielone zerami liczby: 3, 5, 1, 1, 2, a całość danych zakończona jest dwoma zerami)

    Maszyna potrafi tak przemielić tę taśmę, że po zakończeniu jej pracy, będzie ona wyglądała tak:
    101011011101111100
    (1, 1, 2, 3, 5)

    Czyli liczby będą posortowane! W ten sposób da się napisać praktycznie dowolny program.

    Aha, jeszcze jedno. Maszyna Turinga to abstrakcyjny model. Ich budowanie nie ma wielkiego sensu. Maszyn tych używa się za to dość często "na papierze" -- np. żeby udowodnić, że jakiś problem jest nierozstrzygalny.

    Znalezisko pokazuje, że jak się ktoś uprze, to da się to zbudować i z klocków LEGO ;-)

    pokaż komentarz
    Sh1eldeR
  • baby-face +3  

    Takie pierwsze skojarzenie, a co było by jakby tej teoretycznej maszynie zapodać teoretyczną taśmę Moebiusa? Zapętli się?

    pokaż komentarz
    baby-face
  • Sh1eldeR +2  

    @baby-face:
    Wkręciłaby się w teoretyczną głowicę i trzeba by oddać maszynę do teoretycznej naprawy ;-).

    A tak na poważnie to nic szczególnego by się nie stało. Tzn. przewidzenie skutków i możliwości użycia tej wstęgi jako taśmy wykracza poza moje chęci zastanawiania się nad tym. Ale nie sądzę, by maszyna się zapętliła. Tzn. zapętlić jest ją bardzo łatwo i zapętlenie to będzie wynikało nie z taśmy, ale z programu. Wystarczy w funkcji przejścia w jakimś osiąganym stanie napisać, żeby stan się nie zmieniał i żeby wartość bieżącego pola na taśmie też się nie zmieniała. Wtedy ta instrukcja będzie się wykonywała w kółko.

    Jeśli na teoretycznej taśmie zrobisz nawet teoretyczny supełek, to maszyna i tak może się zatrzymać lub nie, zależnie od tego, jak będzie napisany program. Jeśli program uwzględni konstrukcje taśmy, powinno być OK.

    Wstęga Moebiusa jest jednak zamknięta i skończona, a to ogranicza możliwości maszyny Turinga (która jest tak potężna tylko przy nieskończonej taśmie).

    pokaż komentarz
    Sh1eldeR
  • Neratin +1  

    "Wstęga Moebiusa jest jednak zamknięta i skończona, a to ogranicza możliwości maszyny Turinga (która jest tak potężna tylko przy nieskończonej taśmie)."

    Nie do końca rozumiem to stwierdzenie. Obliczenie w sensie Turinga kończy się zawsze po skończonej liczbie kroków, więc zapisana jest zawsze skończona liczba komórek taśmy. Taśma musi być nieograniczona w tym sensie, że jej długość musi wystarczyć aby dane obliczenie mogło zostać wykonane, jednak "potęga" maszyny Turinga polega właśnie na tym, że wszystko co rozumiemy intuicyjnie jako "obliczalne" jest osiągalne przy pomocy skończonych środków (czasowo-pamięciowych).

    pokaż komentarz
    Neratin
  • baby-face -1  

    Ja po prostu uznaje taką teorię, że nieskończoność nie istnieje, prędzej czy później trafi się do punktu wyjścia. To tak, jak z prostą, którą wyznaczają dwa punkty.
    Wg. mnie na kole ;)

    pokaż komentarz
    baby-face
  • w.......s +1  

    I tak mało co zrozumiałem, ale mimo to dziękuje ślicznie. ;*

    pokaż komentarz
    w.......s
  • Sh1eldeR 0  

    @Neratin:
    Zdaje się, że masz rację -- rzeczywiście najwyraźniej chodzi tylko o to, żeby "wszystko, co potrzebne" przy określonym programie i danych nam się na taśmie zmieściło. Taśmę definiuje się jednak jako nieskończoną, w przeciwieństwie do liczby stanów (która może być dowolnie duża, ale skończona).

    pokaż komentarz
    Sh1eldeR
  • sathirem +29  

    Wykop za "Drużynę A" w tle. :P

    pokaż komentarz
    sathirem
  • mbrdej +4  

    Zgadzam, się:) Od razu wyobraziłem sobie czarnego van'a z czerwonym paskiem (i spojlerem!)

    pokaż komentarz
    mbrdej
  • Lukki +3  

    GMC G-Series z 1983 roku :)

    pokaż komentarz
    Lukki
  • anath0r +19  

    nieskończenie długa taśma zapisu w prezencie, ale tylko do wyczerpania zapasów ;]

    pokaż komentarz
    anath0r
  • Kisiol_Ent +4  

    no tak, ale zawsz emozna se 10% tasmy uciag od kolegi, mysle ze wsytarczy do wszystkiego :X

    pokaż komentarz
    Kisiol_Ent
  • kolnay 0  

    Wlasnie tez sie zastanawiam, czy tasma jest nieskonczenie dluga.
    Inaczej to nie chce :

    pokaż komentarz
    kolnay
  • mathix +9  

    Świetne! Wprawdzie trochę nadmiarowe, biorąc pod uwagę, że oparte o mikrokontroler, jednak nie zmienia to faktu, że namacalna maszyna Turinga to coś, o czym za czasów dzieciństwa marzył każdy informatyk :D

    pokaż komentarz
    mathix
  • s..........y +3  

    A ja jeszcze dorzucę maszynę Turinga zrobioną w słynnej grze "Life":
    http://www.cs.unibo.it/babaoglu/courses/cas02-03/papers/Turing-Machine-Life.pdf
    Implementację środowiska dla automatów komórkowych tu: http://golly.sourceforge.net/
    W przykładach znajdziecie maszynę turinga (Signal-Circuitry->Turing_Machine-3-state.rle).

    pokaż komentarz
    s..........y
  • s..........y 0  

    Jestem pod wrażeniem golly: WireWorld->primes.mc

    pokaż komentarz
    s..........y
  • s..........y 0  

    A propos kometarza wyżej: http://www.quinapalus.com/wires11.html

    pokaż komentarz
    s..........y
  • el_che +7  

    Zalezy dla kogo. O Maszynie Turinga uczą chyba na każdych studiach informatycznych. Miło pobawić się czymś takim w realu a nie tylko na kartce :)

    pokaż komentarz
    el_che
  • mGz +11  

    a jak słyszysz na ćwiczeniach o N-taśmowych maszynach Turinga to masz tylko ochotę wyskoczyć oknem z piwnicy. A tutaj proszę przyjemne z pożytecznym. LEGO rox

    pokaż komentarz
    mGz
  • prrrszalony +1  

    Na studiach filozoficznych (epistemologia) też uczą sporo o Turingu. Między innymi o maszynie Turinga.

    pokaż komentarz
    prrrszalony
  • Syntax -1  

    Polecam książkę R. Penrose “Nowe szaty cesarza” Tam jest bardzo przystępnie wyjaśniona idea maszyny turinga i między innymi tzw. problem stopu.

    pokaż komentarz
    Syntax
  • niuton +2  

    Książka Penrose'a nazywa się "Nowy umysł cesarza" (w przeciwieństwie do baśni Andersena ;).

    pokaż komentarz
    niuton
  • pepe88 0  

    po niektórych komentarzasz mam wrażenie że są osoby które myśle że maszyna turinga istanieje :) hmm takie sprostowanie. Maszyna turinga to abstrakcja. Na studiach informatycznych poznajemy jej działanie aby nauczyc sie myśleć algorytmicznie... sam to niestety przeżyłem w tym semestrze pozdro :)

    pokaż komentarz
    pepe88
  • Z.......u 0  

    Prawda, chociaż po obejrzeniu takiego filmiku łatwiej sobie wyobrazić jak to działa. Ba, powiem nawet, że ten filmik bardziej zaciekawił mnie maszyną Turinga niż przenudny wykład PRO.

    pokaż komentarz
    Z.......u
  • za017 0  

    Brak mi słów, mogę tylko napisać: "to jest piękne"

    pokaż komentarz
    za017
  • jeanpaul 0  

    Reklama zestawu lego Mindstorms NXT. Bylem bliski kupna na swieta, ale poczekam jak potanieje - poki co 240Eronow.

    Tutaj wiecej projektow: http://www.nxtprograms.com/

    pokaż komentarz
    jeanpaul
  • ogryzek 0  

    Ta ra ram tam tamtam tam... kto się bawi w "Drużynę A" :) ?
    A tak na serio jak ktoś chce coś takiego zbudować, a nie może (bo żona patrzy, synek nie chce oddać klocków itp) to polecam tren programik:
    http://www.lm-software.com/mlcad/

    Naprawdę świetna zabawa, ale nie jestem pewny czy da się umieścić działające czujniki z Mindstorm.

    pokaż komentarz
    ogryzek
  • Larden 0  

    RAM Machine! to jest to! :D

    pokaż komentarz
    Larden
  • filo86 -3  

    O rany, weźcie sobie poprogramujcie w brainfuck....

    pokaż komentarz
    filo86
  • Sh1eldeR +2  

    Nie żeby powyższy, minusowany obecnie komentarz był wyjątkowo głęboki, ale -- o czym może nie każdy wie -- Brainfuck to istniejący naprawdę, ezoteryczny (tj. mający wywołać u programisty konwulsje ;-)) język programowania. Jeden z najsłynniejszych takich języków i punkt wyjściowy dla wielu innych. Jest bardzo podobny do klasycznej maszyny Turinga.

    http://pl.wikipedia.org/wiki/Brainfuck

    Nawet nie-programiści mogą rzucić okiem na klasyczny przykład: program wyświetlający na ekranie napis "Hello world" wygląda w Brainfucku tak: http://pl.wikipedia.org/wiki/Brainfuck#Hello_World.21

    ...podczas gdy w normalnych językach wystarczy do tego jedna instrukcja typu:
    write('Hello world!'); (plus ew. parę standardowych elementów)

    Teraz już chyba jasne, skąd się wzięła nazwa BF.

    pokaż komentarz
    Sh1eldeR
  • szrek -2  

    ale was to podnieca ;)

    pokaż komentarz
    szrek
  • Sh1eldeR 0  

    Stary, dla informatyków to prawie tak, jakby zobaczyć sanie Świętego Mikołaja... działające i zbudowane z klocków Lego!

    Ok, informatycy dziwni.

    pokaż komentarz
    Sh1eldeR
  • kluczaj88 -2  

    Nie jestem pewnien, ale to chyba jest jakoś sprytnie zmontowany filmik. Wydaje mi się, że około 1min 10sek zębatka porusza się w lewo i w prawo a nie jest to możliwe, gdyż inna część (ta niebieska) powinna ją blokować!

    pokaż komentarz
    kluczaj88
  • darekk1990 -2  

    Nie bądz skąpy, daj minusa...

    pokaż komentarz
    darekk1990
  • signap -2  

    Wykopy poszly za slowo Linux

    pokaż komentarz
    signap
  • Immortal +2  

    Przyjmuję zakłady, ile powyższy komentarz dosatnie plusów/minusów ;)

    pokaż komentarz
    Immortal