 |
Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Kwiatek
pijak
Dołączył: 08 Gru 2005
Posty: 215
Przeczytał: 0 tematów
Skąd: Podkarpacie
|
 Wysłany: Czw 0:16, 02 Lut 2006 Temat postu: Maszyny Turinga |
|
|
|
Czy mógłby mi ktoś wyjaśnić, czym się właściwie różni niedeterministyczna maszyna Turinga od deterministycznej maszyny Turinga? I czy język rozpoznawalny to to samo, co akceptowalny?
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Madras
Omylny Admin
Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów
Skąd: Z Pokoju :]
|
| Wysłany: Czw 0:28, 02 Lut 2006 Temat postu: |
|
|
|
Ja już idę spać ;]. Może Hans wpadnie ;].
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Makros
pijak
Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Czw 0:39, 02 Lut 2006 Temat postu: |
|
|
deterministyczna:
jesteśmy w jakimś stanie np. Q i czytamy znak q i mamy tylko jedno polecenie które nam mówi co teraz możemy zrobić...
niedetrministyczna:
jesteśmy w jakimś stanie np. Q i czytamy znak q i teraz się okazuje że mamy kilka poleceń które do obeznego stanu pasują...
mam nadzieję, ze niczego nie poplątałem...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Czw 0:41, 02 Lut 2006 Temat postu: |
|
|
Niedeterministyczna ma co najmniej jeden stan wewnetrzny (dwójke stan-znakczytany), z którego moze przejsc w kilka różnych stanów. A my nie wiemy jak pójdzie, a ona wie :)
powiedzmy niech bedzie taka maszyna:
...
q,1 -> p,1,L
q,0 -> q,0,R
p,0 -> p,0,L
p,1 -> p,0,L
p,1 -> p,1,R
p,1 -> q,0,S
...
Mniejsza o to co robi (sam nie wiem) ale ważne jest pogrubienie. W tym miejscu mamy niedeterminizm - maszyna moze się znaleźć w kilku różnych stanach! [ A w którym dokładnie to już zadanie dla fizyków teoretycznych i filozofów ;) (polecam książke "Nowy Umysł Cesarza" Rogera Penrose'a :) ) ]
Dla nas wazne jest to że jeśli ta maszyna akceptuje jakiś jezyk i mamy dane dwa słowa do niego należące i dajemy je tej maszynie to ona je zaakceptuje, nawet jeśli zaakceptowanie słowa pierwszego bedzie wymagało w drugim kroku wykonania przejscia p,1 -> p,0,L a nie żadnego innego! Dla nas nieważne jest to że ma kilka dróg do wyboru. Zawsze pójdzie tą właściwą ;) .
Natomiast deterministyczna maszyna jest funkcją. Tzn że jesli mamy taką piatke definiującą ruch: p,1 -> p,0,L to nie możemy zdefiniować jeszcze piatki p,1 -> p,1,R bo to właśnie tą funkcję rozwala.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Czw 0:57, 02 Lut 2006 Temat postu: |
|
|
| Madras napisał: | | Ja już idę spać ;]. Może Hans wpadnie ;]. |
Heh, jak zobaczylem ten post to sobie pomyslalem ze mi sie nie chce odpowiadac, a i tak Madras predzej czy pozniej odpowie :P
No ale do rzeczy.....
Ogolnie maszyna Turinga to jest jakby zbior piatek (stan biezacy, symbol z tasmy, nowy stan, nowy symbol, ruch) i dziala to troche jak przyporzadkowanie: jesli w danym stanie napotkasz dany symbol to przejdz w taki a taki stan (moze byc ten sam), wpisz do tasmy to a to (moze byc to samo :) i przesun sie w lewo, w prawo lub zostan w miejscu. I teraz deterministyczna maszyna Truinga to taka ktora dla kazdej pary (stan, symbol) ktora moze napotkac ma tylko jedna taka piatke. Czyli inaczej mowiac jest scisle okreslone co w danej sytuacji zrobi. Natomiast NDMT (niedeterministyczna maszyna Turinga :P) to taka, ktora dla co najmniej jednej pary (stan, symbol) ma co najmniej dwie mozliwe "czynnosci do wykonania". I teraz dziala to tak ze ta maszyna jak gdyby wie, ktora ma wybrac. Mozemy sobie taka maszyne wyobrazic jako drzewo z rozgalezieniami tam, gdzie jest niedeterminizm. I zakladamy, ze jezeli dostanie na wejsciu cos, co chociaz dla jednej z tych "galezi" da pozytywna odpowiedz to ta szczwana bestia "pojdzie" wlasnie tamtedy... To jest niestety czysta teoria ;) Szkoda ze tak nie ma w rzeczywistosci - ehhh, inteligentne algorytmy :D
Mam nadzieje ze to, co napisalem jest zrozumiale, jak nie to krzyczec :)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Czw 0:59, 02 Lut 2006 Temat postu: |
|
|
O, juz mnie ktos ubiegl... Nawet dwoch ktosiow :)
To nic, zrobilismy sobie takie male kompendium na temat NDMT :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Czw 1:06, 02 Lut 2006 Temat postu: |
|
|
| Cytat: | | To jest niestety czysta teoria Szkoda ze tak nie ma w rzeczywistosci - ehhh, inteligentne algorytmy |
Ale ta teoria ma bardzo silne podstawy w teorii względności i wteorii kwantowej ... ;) . A wogóle to wszystko sprowadza się do nieskończoności, podzbiorów tych nieskończoności i liczenia prawdopodobieństwa [i do liczb zespolonych ;) ] (przynajmniej na tym etapie wiedzy z fizyki jaką znamy...)
Moze w końcu wymyślą jak zbudować ten komputer kwantowy....
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Saimi
pijak
Dołączył: 22 Lis 2005
Posty: 149
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Czw 11:37, 02 Lut 2006 Temat postu: |
|
|
| Robson napisał: | | Ale ta teoria ma bardzo silne podstawy w teorii względności i wteorii kwantowej ... ;) . |
Mam przez to rozumieć, że wybór określonej drogi przez NDTM jest czysto losowy? Znaczy się, że tak naprawdę nie wybiera w jakiś magiczny sposób tej jednej właściwej, tylko idzie wszystkimi, każdą w innym świecie. Hmm... Dobre.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Madras
Omylny Admin
Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów
Skąd: Z Pokoju :]
|
| Wysłany: Czw 11:41, 02 Lut 2006 Temat postu: |
|
|
| Cytat: | | To jest niestety czysta teoria |
No nie do końca, zawsze można zasymulować - tzn. iść po jednym poziomie w górę każdą gałęzią na raz. Tyle, że to będzie na pewno dużo wolniejsze, niż nieistniejąca NDMT ;].
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Czw 12:22, 02 Lut 2006 Temat postu: |
|
|
| Saimi napisał: | | Robson napisał: | | Ale ta teoria ma bardzo silne podstawy w teorii względności i wteorii kwantowej ... ;) . |
Mam przez to rozumieć, że wybór określonej drogi przez NDTM jest czysto losowy? Znaczy się, że tak naprawdę nie wybiera w jakiś magiczny sposób tej jednej właściwej, tylko idzie wszystkimi, każdą w innym świecie. Hmm... Dobre. |
No właśnie tutaj mieszają się fizycy i filozofowie. Bo z ta teorią kwantową to jest właśnie tak jak powiedziałeś: maszyna NDTM idzie sobie wszędzie (a właściwie istnieje) w różnych światach, a kiedy przychodzi wypisać wynik to "przeskakuje" do stanu najbardziej prawdopodobnego(dla naszych danych) :) jak foton który sam jeden moze być traktowany jak wiązka światła - czyli fala rozchodząca się we wszystkie strony :) czyli leci w każdą stronę na raz... ;)
Czysta abstrakcja, ale z naszej strony to w sumie wygląda tak że po prostu ona wie gdzie iśc :)
Aha i tu sie kłania teoria nieskończnie wiele wymiarowej przestrzeni - po prostu taka maszynka idzie w rózne strony (każdy kierunek to inna oś przestrzeni) a keidy my chcemy sprawdzic co policzyła to nastepuje złożenie tych wszystkich wektorów w jeden wypadkowy i to jest nasz wynik :)
To mi się właśnie w fizyce podoba, ale nie chciałbym się uczyć tego wszystkicgo co moi kumple teraz na AGH tylko po to żeby później móc pół roku w ostatnim roku sobie posłuchać takich fajnych filozoficznych wywodów :)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Czw 15:28, 02 Lut 2006 Temat postu: |
|
|
Zalazlem to w sieci i pomyslalem ze moze sie komus przydac przy przygotowaniach do jutrzejszego egzaminu. Ewentualnie do zabawy :D
[link widoczny dla zalogowanych]
|
|
| Powrót do góry |
|
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
