Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

1
Jakie są granice obliczeń w tym wszechświecie?
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 użyte wszystkie atomy we wszechświecie.ππ\pi Jakie są zatem …
5
Czy komputer może symulować się jako część symulowanego świata?
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ć stan wszystkich atomów we Wszechświecie za pomocą komputera, w …
1
Wykonalność maszyn Gödel
Ostatnio natknąłem się na dość interesującą konstrukcję teoretyczną. Tak zwana maszyna Gödela To ogólne narzędzie do rozwiązywania problemów, które jest zdolne do samooptymalizacji. Nadaje się do środowisk reaktywnych. Jak rozumiem, można go zaimplementować jako program do uniwersalnej maszyny Turinga, choć jego wymagania wykraczają daleko poza obecnie dostępny sprzęt. Nie mogłem …
1
W jakim stopniu matematykę Rzeczywistości można zastosować do Rzeczywistości Obliczalnych?
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ą aktualne, biorąc pod uwagę tylko rzeczywiste obliczalne? Bocznym pytaniem jest to, czy wyniki dotyczące liczb obliczalnych …
2
Czy szachy mogą symulować uniwersalną maszynę Turinga?
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 są takie same jak zwykłe szachy minus 50 zasada ruchu, …
3
Czy istnieje nazwa „rzeczy fizycznych, z których można zbudować maszynę Turinga”?
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 Turinga z nieliniowych materiałów optycznych, różnych biomolekuł i kilku innych …
2
Co wiemy o ograniczonych wersjach problemu zatrzymania
( 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 wykrywania zatrzymania jako danych wejściowych. Aby uzyskać więcej informacji, zobacz tło poniżej. Wykazana …
2
Naprawiono punkty w obliczalności i logice
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 twierdzeniami o stałym punkcie w logice a -calculus.λλ\lambda tło 1) Rola …
2
Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną maszynę Turinga?
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 akceptuje L , istnieje również śmiertelna baza TM, która akceptuje …
2
Wyraźne wyrażenie mu-rekurencyjne dla funkcji Ackermana
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 prace Robinsona „Recursion and Double Recursion” i „Primitive Recursive Functions” również …
6
Geometryczna interpretacja obliczeń
Będąc fizyką, zostałem przeszkolony, aby patrzeć na wiele problemów z geometrycznego punktu widzenia. Na przykład geometria różniczkowa rozmaitości w układach dynamicznych itp. Kiedy czytam podstawy informatyki, zawsze staram się znaleźć interpretacje geometryczne. Jak wiarygodna geometryczna interpretacja zbiorów rekurencyjnie wyliczalnych (pracowałem nad częścią, w której próbowałem połączyć je z geometrią algebraiczną, …
2
Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?
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 podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …
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.