Pytania otagowane jako computation-models

Definicja zbioru dopuszczalnych operacji używanych do obliczeń i odpowiadających im kosztów. Niektóre przykłady modeli obejmują maszyny Turinga, funkcje rekurencyjne, rachunek lambda i systemy produkcyjne.

3
Co konkretnie czyni komputery kwantowe użytecznymi?
Wiem, że komputery kwantowe są w stanie przetwarzać superpozycję wszystkich możliwych stanów za jednym przejściem przez logikę. Wydaje się, że to właśnie ludzie wskazują, że komputery kwantowe są wyjątkowe lub przydatne. Jednak po przetworzeniu danych wejściowych superpozycyjnych otrzymujesz wynik superpozycji, którego możesz zadać tylko jedno pytanie, a ono zapada się …
8
Dlaczego możemy założyć, że algorytm może być reprezentowany jako ciąg bitowy?
Zaczynam czytać książkę o złożoności obliczeniowej i maszynach Turinga. Oto cytat: Algorytm (np. Maszyna) może być reprezentowany jako ciąg bitów, gdy zdecydujemy się na pewne kodowanie kanoniczne. To twierdzenie zostało przedstawione jako prosty fakt, ale nie rozumiem tego. Na przykład, jeśli mam algorytm, który przyjmuje jako dane wejściowe i oblicza …
5
Czy interakcja ma większą moc niż algorytmy?
Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem. Jak to może być tak? Jak coś może być mocniejsze niż …
1
Czy nierozwiązywalność problemu N-ciała jest równoważna problemowi zatrzymania
Nie ma ogólnego analitycznego rozwiązania problemu n-ciała, który mógłby wytworzyć funkcję analityczną, która mogłaby zostać użyta do nadania stanu układu n-ciała w dowolnej chwili t z dokładną dokładnością. Istnieją jednak pewne szczególne przypadki układów n-ciała, dla których znana jest funkcja analityczna. W podobny sposób nie ma ogólnego algorytmu, który mógłby …
1
Obliczenia kwantowe - związek między modelem Hamiltonian a modelem Unitary
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 początkowego, a następnie umożliwienie ewolucji systemu zgodnie z równaniem Schrödingera przez pewien czas …
1
Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością
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ę znaleźć na ten temat (Simon 1974, Schonhage 1979) obejmują również operacje …
3
Czy każdy algorytm samodmodyfikujący może być modelowany za pomocą algorytmu niemodyfikującego?
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: Ok, więc dowód, że jest to możliwe, …
2
Dlaczego maszyny Turinga liniowo ograniczone są bardziej wydajne niż automaty o stanie skończonym?
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 kontekst. Oczywiście czegoś tu brakuje. Co się dzieje?
3
Pojęcia wydajnego obliczenia
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 na maszynach Turinga Nie znam jednak solidnej teorii do analizy złożoności obliczeniowej …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
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 rozwiązać …
3
Obliczenia nieskończone w czasie skończonym
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 czasie.jathjathi^\text{th}1 / 2ja1/2)ja1/2^i Dlaczego to jest niemożliwe? Czy istnieje dolna granica czasu potrzebnego do …
1
Czy niedeterminizm w niedeterministycznej maszynie Turinga różni się od automatów skończonych i automatów wypychających?
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 istnienie w sss, jeśli istnieje przejście tego …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.