Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

1
Problem zatrzymania, niepoliczalne zbiory: wspólny dowód matematyczny?
Wiadomo, że z policzalnym zestawem algorytmów (charakteryzujących się liczbą Gödla) nie możemy obliczyć (zbudować algorytmu binarnego, który sprawdza przynależność) wszystkich podzbiorów N. Dowód można podsumować w następujący sposób: jeśli moglibyśmy, to zestaw wszystkich podzbiorów N byłby policzalny (moglibyśmy powiązać z każdym podzbiorem liczbę Gödla algorytmu, który go oblicza). Ponieważ jest …
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 …
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 …
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 …
6
Jak określa się liczby rzeczywiste w obliczeniach?
To może być podstawowe pytanie, ale czytałem i próbowałem zrozumieć artykuły na takie tematy, jak obliczenia równowagi Nasha i liniowe testy degeneracji, i nie byłem pewien, jak liczby rzeczywiste są określone jako dane wejściowe. Na przykład, kiedy stwierdzono, że LDT ma pewne dolne granice wielomianu, w jaki sposób określa się …
4
Twierdzenie Kościoła i twierdzenia o niekompletności Gödla
Niedawno czytałem o niektórych pomysłach i historii przełomowej pracy wykonanej przez różnych logików i matematyków w zakresie obliczeń. Podczas gdy poszczególne koncepcje są dla mnie dość jasne, staram się dobrze zrozumieć wzajemne relacje i abstrakcyjny poziom, na którym wszystkie są ze sobą powiązane. Wiemy, że twierdzenie Kościoła (a raczej niezależne …
4
Czy istnieje niepełny model Turinga, którego problem zatrzymania jest nierozstrzygalny?
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 stopniu zaawansowania
2
W jakim stopniu algorytm może przewidzieć złożoność czasową dowolnego programu wejściowego?
Powstrzymanie problemu twierdzi, że niemożliwe jest napisanie programu, który może określić, czy kolejne przystanków programowych dla wszystkich możliwych programów wejściowych . Mogę jednak z pewnością napisać program, który może obliczyć czas działania programu takiego jak: for(i=0; i<N; i++) { x = 1; } i zwróć czasową złożoność , bez uruchamiania …
3
Czy istnieje wynik w teorii obliczalności, która nie jest relatywizowana?
Czytałem artykuł Andreja Bauera Pierwsze kroki w teorii obliczeń syntetycznych . Na zakończenie zauważa to Nasza aksjatyzacja ma swoje granice: nie może udowodnić żadnych wyników w teorii obliczeń, które nie relatywizują się do obliczeń wyroczni. Jest tak, ponieważ teorię można interpretować jako wariant efektywnego toposu zbudowanego z częściowych funkcji rekurencyjnych …
5
Problem z obliczalnością nauczania
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 nauczę ich maszyn Turinga, a następnie odpowiem „funkcja jest obliczalna, …
3
Jeśli abstrakcyjna maszyna może się symulować, czy to czyni Turinga kompletnym?
Na przykład w językach programowania często pisze się kompilator / interpreter X-w-X, ale na bardziej ogólnym poziomie wiele znanych systemów Turing-complete może symulować się w imponujący sposób (np. Symulując grę życia Conwaya w grze życia Conwaya ). Moje pytanie brzmi zatem: czy system jest w stanie samodzielnie przeprowadzić symulację, aby …
2
normalne zachowanie maszyn Turinga
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 wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow …
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.