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),...
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(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME...
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 ,...
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...
To jest przeformułowanie Czy programy gramatyczne? poprzednio zadane przez Vag i z wieloma sugestiami komentujących. W jaki sposób można postrzegać gramatykę jako model obliczeń? Jeśli na przykład weźmiemy prostą gramatykę bezkontekstową, taką jak G ::= '1' -> '0' '+' '1' '1' -> '1' '+'...
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:...
Czy są jakieś praktyczne zastosowania dla modeli programowania innych niż von Neumann? Jakie są najczęściej stosowane języki programowania inne niż von
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...
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...
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...
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ą...
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...
Naprawmy kodowanie maszyn Turinga i uniwersalnej maszyny Turinga U, która na wejściu (T, x) wypisuje dowolne T na wejściu x (być może oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla x, K (x), jako długość najkrótszego programu, p, tak aby U (p) = x. Czy istnieje takie N, że dla...