Rozumiem, że kompletność Turinga wymaga nieograniczonej pamięci i nieograniczonego czasu. Jednak w tej usłudze jest skończona ilość atomów, co ogranicza pamięć. Na przykład, chociaż jest irracjonalne, nie ma sposobu na przechowywanie więcej niż pewnej liczby cyfr, nawet jeśli do tego celu zostały...
Hyperkomputer odnosi się do modeli obliczeniowych, których nie można symulować za pomocą maszyn Turinga. (Hyperkomputery niekoniecznie są fizycznie możliwe do zrealizowania!) Niektóre hiperkomputery mają dostęp do zasobu, który pozwala na rozwiązanie problemu zatrzymania dla standardowych maszyn...
Wiele twierdzeń i „paradoksów” - przekątna Cantora, nierozstrzygalność nienawiści, nierozstrzygalność złożoności Kołmogorowa, niekompletność Gödela, niekompletność Chaitina, paradoks Russella itp. - wszystkie mają w zasadzie ten sam dowód po przekątnej (zauważ, że jest to bardziej specyficzne niż...
Fraktalny labirynt to labirynt, który zawiera swoje kopie. Np. Następujący Mark Mark Wolf z tego artykułu : Zacznij od MINUS i przejdź do PLUS. Po wprowadzeniu mniejszej kopii labiryntu zapisz jej nazwę literową, ponieważ będziesz musiał pozostawić tę kopię przy wyjściu. Musisz wyjść z każdej...
Szukam najmniejszego możliwego uniwersalnego kombinatora , mierzonego liczbą abstrakcji i aplikacji wymaganych do określenia takiego kombinatora w rachunku lambda . Przykłady uniwersalnych kombinatorów obejmują: rozmiar 23: λf.f (fS (KKKI)) K. rozmiar 18: λf.f (fS (KK)) K. rozmiar 14:...
Załóżmy, że budujesz komputer, który będzie obliczał stan wszystkich atomów we Wszechświecie w pewnym momencie w przyszłości. Ponieważ Wszechświat jest z definicji wszystkim, co istnieje (i wszystkim, co wchodzi w interakcję z resztą), obejmuje także komputer, który budujesz. Czy potrafisz obliczyć...
( AKTUALIZACJA : postawiono tutaj lepiej sformułowane pytanie , ponieważ komentarze do przyjętej odpowiedzi poniżej pokazują, że to pytanie nie jest dobrze zdefiniowane) Klasyczny dowód na niemożność problemu zatrzymania zależy od wykazania sprzeczności przy próbie zastosowania algorytmu...
Czy istnieje ogólne twierdzenie, które przy odpowiedniej dezynfekcji stanowiłoby, że najbardziej znane wyniki dotyczące użycia liczb rzeczywistych mogą być rzeczywiście wykorzystane przy rozważaniu tylko liczb rzeczywistych? Czy też istnieje właściwa charakterystyka wyników, które pozostają...
Szukam konkretnej odpowiedzi na pytanie tytułowe. Czy istnieje zbiór zasad, które przekładają dowolny program na konfigurację skończonych elementów na nieskończonej planszy, tak że jeśli czarno-biały gra tylko legalne ruchy, gra kończy się w skończonym czasie, jeśli program się zatrzymuje? Zasady...
Każdy język, który nie jest kompletny w Turingu, nie może napisać dla siebie tłumacza. Nie mam pojęcia, gdzie to przeczytałem, ale widziałem, że używał go wiele razy. Wydaje się, że prowadzi to do pewnego rodzaju „ostatecznego” pełnego języka Turinga; te, które mogą tylkobyć interpretowanym przez...
Jedną z niesamowitych rzeczy w informatyce jest to, że fizyczne wdrożenie jest w pewnym sensie „nieistotne”. Ludzie z powodzeniem zbudowali komputery z kilku różnych podłoży - przekaźników, lamp próżniowych, dyskretnych tranzystorów itp. Ludzie mogą wkrótce odnieść sukces w budowie komputerów...
Biorąc pod uwagę język L zdefiniowany przez maszynę Turinga, która go decyduje, czy możliwe jest algorytmiczne określenie, czy L leży w
To pytanie zostało również opublikowane na Math.SE, /math/1002540/fixed-points-in-computability-nd-logic Mam nadzieję, że opublikowanie go tutaj jest również w porządku. Jeśli nie, lub jeśli jest to zbyt podstawowe dla CS.SE, powiedz mi, a ja go usunę. Chciałbym lepiej zrozumieć związek między...
Czy mógłbyś wskazać, jak zbudować funkcję Ackermana (tak naprawdę interesuje mnie wersja zaproponowana przez Rózsa Pétera i Raphaela Robinsona) za pomocą standardowych operatorów rekursywnych? Próbowałem oryginalnych prac Pétera i Robinsona, ale praca Pétera używa języka innego niż angielski, a...
Mówimy, że maszyna Turinga jest śmiertelna, jeśli M zatrzymuje się przy każdej początkowej konfiguracji (w szczególności zawartość taśmy i stan początkowy mogą być dowolne). Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną Maszynę Turinga? (tzn. jeśli istnieje baza TM, która...
Od dawna wiadomo, że przy dowolnym stopniu reuringu istnieje dobrze przedstawiona grupa, której problem słowny jest w tym stopniu. Moje pytanie brzmi, czy to samo dotyczy dowolnych stopni Turinga w czasie wielomianowym . W szczególności, biorąc pod uwagę rozstrzygalny zestaw, , czy istnieje...
Greg Egan w swojej powieści „Dark Integers” (opowieść o dwóch wszechświatach z dwiema różnymi matematykami komunikującymi się poprzez dowodzenie twierdzeń o niespójności arytmetycznej) twierdzi, że możliwe jest zbudowanie komputera ogólnego przeznaczenia wyłącznie na istniejących routerach...
Dwa dokumenty, które chciałbym załączyć to: D. Kozen, „Indeksowanie klas subrekursywnych” , STOC, 1978. R. Ladner, „O strukturze wielomianowej redukcji czasu” , JACM,
Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco...
Twierdzenie Rice'a stwierdza, że każda nietrywialna właściwość zbioru rozpoznawana przez niektóre maszyny Turinga jest nierozstrzygalna. Szukam teoretycznego złożoności twierdzenia typu Rice, które mówią nam, które nietrywialne właściwości zbiorów NP są trudne do...