Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

2
Dark Integers: Obliczenia ogólnego przeznaczenia na routerach internetowych
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 internetowych przy użyciu tylko jego podstawowej funkcjonalności przełączania pakietów (a dokładniej korekty sumy kontrolnej). Czy …
1
Odstęp między
HT(n)HT(n)HT(n)nnnBB(n)=maxHT(n)BB(n)=maxHT(n)BB(n) = \max HT(n) Co możemy powiedzieć o drugiej największej liczbie w ? Nazwij to .HT(n)HT(n)HT(n)BB2(n)BB2(n)BB_2(n) BB2(n)BB2(n)BB_2(n) jest banalnie nieobliczalny, ponieważ pozwala obliczyć : wystarczy poczekać, aż zatrzyma się jeszcze jedna maszyna. Naiwnie oczekiwałbym, że przerwa będzie „zajęta jak bóbr”, rosnąc szybciej niż jakakolwiek funkcja obliczalna. Czy to da się …
3
Dowód nierozstrzygalności, a nie redukcja problemu zatrzymania
Zwykłym sposobem udowodnienia nierozstrzygalności jest redukcja problemu RE-zupełnego, takiego jak problem zatrzymania, trafność w logice pierwszego rzędu, spełnienie równań diofantycznych itp. Wiadomo, że istnieją rekurencyjnie wyliczalne, ale nierozstrzygalne problemy, które nie są uzupełniane ponownie, ale są to sztuczne konstrukcje (to znaczy zestawy, które zostały zdefiniowane tylko w celu pokazania tego …
3
Czy każdy program można wdrożyć mechanicznie?
Czy można zbudować mechaniczną implementację powiedzmy Microsoft Word w jednym celu (bez Turinga)? Czy można wdrożyć takie rzeczy jak iteratory, funkcje pierwszego rzędu, całą gamę technik programowania? Czy koła zębate i inne części mechaniczne mogą reprezentować struktury danych, a nawet obiekty programu? Czy w pewnym momencie wymaga to zbudowania maszyny …
1
Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …
2
Jak dokładnie rachunek lambda uwzględnia intuicyjne pojęcie obliczalności?
Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?λλ\lambda „Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.λλ\lambda Załóżmy, że bazy danych nie istnieją - jak więc można „intuicyjnie” przekonać się o zdolności …
1
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej maszyny język rozpoznawany / definiowany przez tę maszynę jest pusty. Tutaj opis …
2
Ograniczenie pytań progowych do pytań skończoności
Zwykle łatwiej jest uzasadnić rachunek różniczkowy, w którym ograniczeniem jest skończoność obliczeń, a nie próg taki jak „obliczalny w wielomianowym czasie”. Na przykład w teorii języków formalnych, zamiast używać aby scharakteryzować aperiodic monoïd, łatwiej jest używać profinite wyrazów, aby .x ω + 1 = x ω∃ n . xn + …
5
Czy istnieją rozstrzygalne problemy, dla których w przypadku braku algorytmu nie możemy ustalić granic czasowych?
Czy istnieją rozstrzygalne problemy, takie że dla żadnego algorytmu, który nie rozwiązałby problemu, możemy wyznaczyć limit czasowy jako funkcję długości n instancji wejściowej? Doszedłem do tego pytania, ponieważ myślałem o następujących kwestiach: Załóżmy, że mamy rekurencyjnie wymienny, ale nierozstrzygalny problem. Załóżmy dalej, że jestem przyczyną problemu „tak”. Następnie, dla żadnego …
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
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.