Pytania otagowane jako universal-computation

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 …
3
Uzasadnienie logarytmu f w twierdzeniu o hierarchii DTIME
Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną: DTIME(flogf)⊊DTIME(f)DTIME(flog⁡f)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME DSPACE. Podstawowe uzasadnienie wynika ze szczegółów dowodu, biorąc pod uwagę różnicę między symulatorami. Moje pytanie jest następujące: bez …
2
Czy nie możemy przedstawić złożoności Kołmogorowa?
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx , K(x)K(x)K(x) , jako długość najkrótszego programu ppp tak aby …
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
Najmniejszy możliwy uniwersalny kombinator
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: λf.fKSK rozmiar 12: λf.fS (λxyz.x) rozmiar 11: λf.fSK gdzie S = λxyz.xz …
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
Funkcja, która ma być jednokierunkowa, jeśli istnieją funkcje jednokierunkowe?
Istnieje stara sztuczka polegająca na spisaniu algorytmu, który, jeśli P = NP, rozwiązuje SAT w czasie wielomianowym. Zasadniczo, wymieniono wszystkie wielomianowe wehikuły czasu i wielozadaniowość nad nimi. Czy istnieje analogiczna sztuczka dla funkcji jednokierunkowych (a nawet jednokierunkowych funkcji zapadni)? Czy możemy zapisać funkcję, która, jeśli istnieją funkcje jednokierunkowe, jest koniecznie …
1
Czy uczeń Alana Turinga, Robin Gandy, stwierdził, że Charles Babbage nie ma pojęcia o uniwersalnej maszynie komputerowej?
Robin Gandy był uczniem Alana Turinga . Gandy przeprowadził analizę silnika analitycznego Babbage'a (patrz „Gandy - zbieżność pomysłów w 1936 r.” Cytowany w „Herken, Rolf - Uniwersalna maszyna Turinga - badanie półwiecze. Springer Verlag”) - i powiedział, że tak (por. s. 52–53): Funkcje arytmetyczne +, -, ×, gdzie - oznacza …
2
Ograniczanie wpisów operatorów jednolitych do liczb rzeczywistych i uniwersalnych zestawów bramek
W Bernsteina i Vazirani w przełomowej pracy „Quantum Theory Complexity”, pokazują, że redd wymiarowa przekształcenie unitarne można skutecznie przybliżony przez iloczyn co nazywają „w pobliżu trywialna obroty” i „przesunięcia fazowe niemal trywialne”. „Near-trywialne obrotów” oznaczają wymiarową jednolity macierzy, które działają jako identyczności na wszystkich jednak 2 wymiarach, lecz działają jako …
2
Czy istnieje oficjalna nazwa pojęcia „uniwersalnego użytku”?
Istnieje kilka różnych (prawdopodobnie nierównych) pojęć uniwersalności obliczeniowej (patrz na przykład kilka ostatnich stron http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) i nie ma zgody między eksperci o tym, które pojęcia są najbardziej poprawne (patrz na przykład http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ). Próbuję powiedzieć coś o konkretnym modelu obliczeń biomolekularnych. Chciałbym argumentować, że jest „bardziej uniwersalny” lub „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.