Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

15
Prosty problem, którego rozstrzygalność nie jest znana
Przygotowuję się do wykładu skierowanego do studentów kierunków matematycznych, w ramach których rozważam omówienie koncepcji rozstrzygalności. Chcę podać przykład problemu, o którym obecnie nie wiemy, że jest rozstrzygalny lub nierozstrzygalny. Istnieje wiele takich problemów, ale jak dotąd żaden z nich nie wyróżnia się na tle innych. Co to jest prosty …
10
Co to znaczy obalić tezę Turinga?
Przepraszam za chwytliwy tytuł. Chcę zrozumieć, co należy zrobić, aby obalić tezę Turinga? Gdzieś czytam, że jest to matematycznie niemożliwe! Dlaczego? Turing, Rosser itp. Użyli różnych terminów, aby rozróżnić: „co można obliczyć” i „co można obliczyć za pomocą maszyny Turinga”. Definicja Turinga z 1939 r. Jest następująca: „Użyjemy wyrażenia„ funkcja …
3
Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem płytek są często nierozstrzygalne (np. Czy ta płytka poliomino ma jakiś prostokąt?), …
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 …
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: { …
4
Czy są jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samoreferencji lub diagonalizacji?
To pytanie jest z tym związane . Po wielu rozmowach po raz kolejny, w znacznie prostszej formie, wydawało się, że to zupełnie inne pytanie. Klasyczny dowód nierozstrzygalności problemu zatrzymania zależy od wykazania sprzeczności przy próbie nałożenia na siebie hipotetycznego decydenta HALT. Myślę, że oznacza to po prostu niemożność posiadania decydenta …
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 …
9
Jaka jest różnica między niedeterminizmem a przypadkowością?
Niedawno to usłyszałem - „Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”. Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)? Edycja 1: Aby wyjaśnić, cytat …
7
Co wiemy o możliwych do udowodnienia poprawnych programach?
Coraz większa złożoność programów komputerowych i coraz ważniejsza pozycja komputerów w naszym społeczeństwie sprawia, że ​​zastanawiam się, dlaczego nadal nie używamy zbiorowo języków programowania, w których musisz formalnie udowodnić, że kod działa poprawnie. Uważam, że termin ten jest „kompilatorem certyfikującym” (znalazłem go tutaj ): kompilatorem kompilującym język programowania, w którym …
4
Zgodność między klasami złożoności a logiką
Raz wziąłem klasę na temat obliczalności i logiki. Materiał zawiera korelację między klasami złożoności / obliczalności (R, RE, co-RE, P, NP, Logspace, ...) i Logiką (rachunek predykatów, logika pierwszego rzędu, ...). Korelacja obejmowała kilka wyników w jednym polu, które zostały uzyskane przy użyciu technik z drugiego pola. Przypuszczano, że P! …
5
Języki programowania dla wydajnych obliczeń
Niemożliwe jest napisanie języka programowania, który zezwala wszystkim maszynom, które zatrzymują się na wszystkich wejściach i żadnych innych. Wydaje się jednak, że łatwo jest zdefiniować taki język programowania dla dowolnej standardowej klasy złożoności. W szczególności możemy zdefiniować język, w którym możemy wyrazić wszystkie wydajne obliczenia i tylko wydajne obliczenia. Na …
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 …
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.