Pytania otagowane jako turing-machines

Maszyna Turinga to podstawowy model obliczeń, szczególnie w pracy teoretycznej.

2
Teoria wykonalności: różnica mocy między rachunkiem lambda a maszynami Turinga
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: Jeśli jednak użyjemy rachunku lambda, wówczas [program] c …
5
Historyczne przyczyny przyjęcia maszyny Turinga jako podstawowego modelu obliczeń.
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 pierwsze pojawiło się dopiero później, a drugie …
10
Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?
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 do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?
2
Alfabet maszyny Turinga z pojedynczą taśmą
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: { …
7
Naprawdę generator liczb losowych: obliczanie Turinga?
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 mówi w swojej odpowiedzi: „To [losowości Martina-Löfa] nie może być wygenerowane przez maszynę”. …
7
Możliwość zastosowania tezy Church-Turinga do interaktywnych modeli obliczeniowych
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 rzeczywistości dotyczy on tylko obliczeń funkcji, które …
3
Wyjaśnienie klas P i NP za pomocą rachunku lambda
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 modelu obliczeń), ale nigdy nie widziałem wyjaśnienia …
3
Ograniczenia maszyny Turinga, które sprawiają, że zatrzymanie jest rozstrzygalne
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 powtórzyć.SSSQQQSSS Czy istnieją inne naturalne ograniczenia dotyczące maszyny Turinga, które sprawiają, że …
6
Jaka jest najprostsza 2-stanowa uniwersalna maszyna Turinga bez kontrowersji?
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), że istnieją kontrowersje dotyczące tego, czy maszyna …
4
Czy probabilistyczna maszyna Turinga może rozwiązać problem zatrzymania?
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 komputer probabilistyczny robi coś, czego deterministycznie nie można: Rozważmy mały program (o długości mniejszej …
1
Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć
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 się go nauczyć z wielomianową złożonością próbki …
2
Jakich funkcji nie może obliczyć System F?
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 komputerowych przy wykrywaniu większej liczby błędów. Jaki jest …
1
Czy istnieje rozsądny zautomatyzowany system dowodowy dla twierdzeń TCS?
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 o kodowaniu jednego, ale brakowało tego samouczka, a język był …
6
Maksymalna moc obliczeniowa implementacji C.
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 zachowanie zdefiniowane w implementacji. Implementacja AC nie musi być w stanie …
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.