Podczas opracowywania algorytmów obliczeń kwantowych zauważyłem, że istnieją dwa podstawowe modele, w których odbywa się to. Niektóre algorytmy - takie jak problem drzewa Hamiltonian NAND (Farhi, Goldstone, Guttman) - działają poprzez zaprojektowanie stanu hamiltonowskiego i pewnego stanu...
Próbuję zrozumieć istnienie języków nierozpoznawalnych. Aby to uzyskać, muszę wiedzieć, dlaczego maszyna Turinga rozpoznaje tylko jeden język, a nie wiele. Dlaczego
Literatura jest dość jasna, że jednostronne pamięci RAM z pierwotnym mnożeniem są nieuzasadnione, ponieważ są nie mogą być symulowane przez maszyny Turinga w czasie wielomianowym potrafi rozwiązać problemy związane z PSPACE w czasie wielomianowym Jednak wszystkie odniesienia, które mogę...
Jeśli mamy dowolny dowolny program komputerowy, który może modyfikować jego instrukcje, czy można symulować ten program za pomocą programu, który nie może modyfikować jego instrukcji? Edytować: Jestem nowy w stosie wymiany, więc nie jestem pewien, czy mogę zadawać NOWE pytanie tutaj, ale oto:...
Zastanawiałem się, dlaczego taśma / taśmy nie są częścią formalnej definicji maszyny Turinga. Rozważmy na przykład formalną definicję maszyny Turinga na stronie Wikipedii . Definicja, po Hopcroft i Ullman, obejmuje: skończony zestaw stanów , alfabet taśmy Γ , pusty symbol b ∈ Γ , stan początkowy q...
Miałem wrażenie, że nasze komputery, będąc skończone, ostatecznie nie są potężniejsze niż (wyjątkowo duże) skończone maszyny stanowe. Jednak maszyny Turinga liniowo ograniczone są również skończone, ale wydaje się, że zwykłe języki są ściśle niewłaściwym podzbiorem języków wrażliwych na...
Algorytm maszyny Turinga w czasie wielomianowym jest uważany za wydajny, jeśli jego czas działania, w najgorszym przypadku, jest ograniczony przez funkcję wielomianu w wielkości wejściowej. Mam świadomość silnej tezy Kościoła-Turinga: Każdy rozsądny model obliczeń może być skutecznie symulowany...
Jest to prawdopodobnie głupia myśl, ale załóżmy, że mamy komputer, który jest zaprogramowany do wykonywania nieskończonej sekwencji obliczeń i załóżmy, że wykonanie obliczenia zajmuje sekundy sekundę. Następnie ten komputer może wykonać nieskończoną liczbę obliczeń w skończonym...
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to...
Niech łańcuch wejściowy będzie podany jako w1w2...wnw1w2...wnw_1w_2...w_n. Następnie, jeśli NFA jest obecnie w stanierrr (i przeczytał wejście do alfabetu wiwiw_i ), a następnie przed odczytaniem następnego symbolu wejściowego NFA dzieli się na dwa NFA, z których jeden jest w stanie rrr i inne...
Według mojej wiedzy nie istnieje algorytm najgorszego przypadku, który rozwiązuje następujący problem:O ( n )O(n)O(n) Biorąc pod uwagę ciąg długości składający się ze skończonych liczb całkowitych, znajdź permutację, w której każdy element jest mniejszy lub równy jego następcy.nnn Ale czy...
Jest to kontynuacja kolejnego pytania tutaj i mam nadzieję, że nie jest to zbyt filozoficzne. Jak zauważył Raphael w komentarzu do mojego poprzedniego pytania, tak naprawdę nie rozumiem definicji „obliczalnego”, ale zgodnie z niektórymi artykułami, które czytam, definicja nie jest również bardzo...
Chciałbym zacytować Nielsen & Chuang, Obliczenia kwantowe i informacje kwantowe, wydanie z okazji 10. rocznicy, strona 5 (moje wyróżnienie): Jedna klasa wyzwań dla silnej tezy Kościoła i Turinga pochodzi z dziedziny obliczeń analogowych. Przez lata od Turinga wiele różnych zespołów naukowców...
W poprzednim pytaniu Czym dokładnie jest algorytm? , Zapytałem, czy posiadanie „algorytmu”, który zwraca wartość funkcji opartej na tablicy wstępnie obliczonych wartości, jest algorytmem. Jedną z odpowiedzi, która zwróciła moją uwagę, była ta: Przykład silni wchodzi w inny model obliczeń, zwany...