Maszyna Turinga to podstawowy model obliczeń, szczególnie w pracy teoretycznej.
Czy istnieje związek między Maszyną Turinga a rachunkiem lambda - czy zdarzyło się, że powstały mniej więcej w tym samym
Mam trzy powiązane pytania, które są zaznaczone punktorami poniżej (nie, nie można ich podzielić, jeśli się zastanawiasz). Andrej Bauer napisał tutaj , że niektóre funkcje można realizować za pomocą maszyny Turinga, ale nie za pomocą rachunku lambda. Kluczowym krokiem jego rozumowania jest:...
Rozumiem, że model Turinga stał się „standardem” przy opisywaniu obliczeń. Interesuje mnie, dlaczego tak jest - to znaczy, dlaczego model TM stał się szerzej stosowany niż inne teoretycznie równoważne (o ile mi wiadomo) modele, na przykład μ-Recursion Kleene'a lub rachunek lambda (rozumiem to...
Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu...
Czy każda funkcja która jest obliczalna w czasie t na maszynie Turinga z pojedynczą taśmą, używając alfabetu wielkości k = O ( 1 ), może być obliczona w czasie O ( t ) na single-taśma maszyna Turinga za pomocą alfabetu wielkości 3 (powiedzmy, 0 , 1 , i puste)?fa: { 0 , 1 }∗→ { 0 , 1...
Szukam ostatecznej odpowiedzi na pytanie, czy generowanie „prawdziwie losowych” liczb jest obliczalne przez Turinga. Nie wiem, jak to dokładnie sformułować. Pytanie StackExchange dotyczące „wydajnych algorytmów do generowania liczb losowych” jest bliskie odpowiedzi na moje pytanie. Charles Stewart...
Paul Wegner i Dina Goldin od ponad dekady publikują artykuły i książki, argumentując przede wszystkim, że teza o Kościele Turinga jest często fałszywie przedstawiana w społeczności CS Teorii i gdzie indziej. Oznacza to, że jest prezentowany jako obejmujący wszystkie obliczenia, podczas gdy w...
We wstępie i wyjaśnieniach klasy złożoności P i NP często podawane przez maszynę Turinga. Jednym z modeli obliczeń jest rachunek lambda. Rozumiem, że wszystkie modele obliczeń są równoważne (i jeśli możemy wprowadzić coś w kategoriach maszyny Turinga, możemy wprowadzić to w kategoriach dowolnego...
Jeśli ograniczy się maszyny Turinga do skończonej taśmy (tj. Do zastosowania ograniczonej przestrzeni ), wówczas problem zatrzymania jest rozstrzygalny, zasadniczo dlatego, że po kilku etapach (które można obliczyć na podstawie liczby stanów i oraz rozmiar alfabetu), konfigurację należy...
Chcę zakodować prostą maszynę Turinga w zasadach gry w karty. Chciałbym uczynić ją uniwersalną maszyną Turinga, aby udowodnić jej kompletność. Do tej pory stworzyłem stan gry, który koduje 2-stanową, 3-symbolową maszynę Turinga Alexa Smitha . Wydaje się jednak (co prawda na podstawie Wikipedii),...
Komputer z nieskończonym strumieniem naprawdę losowych bitów jest potężniejszy niż komputer bez niego. Pytanie brzmi: czy jest wystarczająco silny, aby rozwiązać problem zatrzymania? Czy komputer probabilistyczny może ustalić, czy program deterministyczny przestaje działać? Przykład, w którym...
Jeśli przejdziemy do tej książki (lub innej wersji specyfikacji języka, jeśli wolisz), ile mocy obliczeniowej może mieć implementacja języka C? Należy zauważyć, że „implementacja C” ma znaczenie techniczne: jest to szczególna instancja specyfikacji języka programowania C, w której udokumentowano...
W tym artykule na Wikipedii o kompletności Turinga stwierdza się, że: Rachunek lambda bez typu jest zakończony przez Turinga, ale wiele typowych rachunków lambda, w tym System F, nie jest. Wartość typowanych systemów polega na ich zdolności do reprezentowania najbardziej typowych programów...
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można...
Załóżmy, że chciałem sformalizować dowód Turinga dotyczący problemu zatrzymania, aby maszyna mogła to sprawdzić. Niektóre ze znanych automatycznych systemów dowodzenia twierdzeń obejmują Mizar, Coq i HOL4. Pobrałem i eksperymentowałem z Coq, ale nie ma biblioteki dla maszyn Turinga. Sam pomyślałem...
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx ,...
Nie mogę wymyślić żadnego takiego modelu, może jakiejś formy wypisanego rachunku lambda? jakiś elementarny automat komórkowy? To prawie obaliłoby „zasadę równoważności obliczeniowej” Wolframa: Prawie wszystkie procesy, które nie są oczywiście proste, można postrzegać jako obliczenia o podobnym...
Zdaję sobie sprawę z bardzo konkretnego pytania i wątpię, że odpowie na nie każdy, kto nie jest zaznajomiony z zasadami Magii. Przeniesiony do Draw3Cards . Oto kompleksowe zasady gry Magic: the Gathering . Zobacz to pytanie, aby uzyskać listę wszystkich magicznych kart. Moje pytanie brzmi - czy gra...
Mam trudności z nauczeniem pojęcia funkcji obliczalnych. Próbowałem rozwinąć pojęcie, dlaczego badacze tacy jak Hilbert / Ackermann / Godel / Turing / Church / ... wymyślili pojęcie „obliczalności”. Uczniowie natychmiast zapytali: „co oznacza obliczalność?” i nie mogę odpowiedzieć, dopóki nie...
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem...