:]

Ciastka!

Strona korzysta z plików cookies w celu realizacji usług i zgodnie z Polityką Plików Cookies. Możesz określić warunki przechowywania lub dostępu do plików cookies w Twojej przeglądarce.

  •  

    pokaż komentarz

    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

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

    •  

      pokaż komentarz

      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

      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

      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

      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

      [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

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

    •  

      pokaż komentarz

      @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

      "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

      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

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

    •  

      pokaż komentarz

      @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

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    Ś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

    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

    Sztuka dla sztuki.

  •  

    pokaż komentarz

    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

    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

      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

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

  •  

    pokaż komentarz

    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

    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

    RAM Machine! to jest to! :D

  •  

    pokaż komentarz

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

    •  

      pokaż komentarz

      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

    ale was to podnieca ;)

  •  

    pokaż komentarz

    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

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

  •  

    pokaż komentarz

    Wykopy poszly za slowo Linux

  •  

    pokaż komentarz

    WOW, swietny serwis ten wykop :D juz wiem co bede robila w pracy przez najblizszy tydzien :D :D :D trzeba przesledzic caly 2008 rok :)

    Uwielbiam lego, moj synek tez :)