Pytania otagowane jako turing-machines

Maszyna Turinga to podstawowy model obliczeń, szczególnie w pracy teoretycznej.

4
Twierdzenie Kościoła i twierdzenia o niekompletności Gödla
Niedawno czytałem o niektórych pomysłach i historii przełomowej pracy wykonanej przez różnych logików i matematyków w zakresie obliczeń. Podczas gdy poszczególne koncepcje są dla mnie dość jasne, staram się dobrze zrozumieć wzajemne relacje i abstrakcyjny poziom, na którym wszystkie są ze sobą powiązane. Wiemy, że twierdzenie Kościoła (a raczej niezależne …
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
3
Czy Magic: the Gathering Turing jest ukończony?
Zdaję sobie sprawę z bardzo konkretnego pytania i wątpię, że odpowie na nie każdy, kto nie jest zaznajomiony z zasadami Magii. Przeniesiony do Draw3Cards . Oto kompleksowe zasady gry Magic: the Gathering . Zobacz to pytanie, aby uzyskać listę wszystkich magicznych kart. Moje pytanie brzmi - czy gra Turing jest …
5
Problem z obliczalnością nauczania
Mam trudności z nauczeniem pojęcia funkcji obliczalnych. Próbowałem rozwinąć pojęcie, dlaczego badacze tacy jak Hilbert / Ackermann / Godel / Turing / Church / ... wymyślili pojęcie „obliczalności”. Uczniowie natychmiast zapytali: „co oznacza obliczalność?” i nie mogę odpowiedzieć, dopóki nie nauczę ich maszyn Turinga, a następnie odpowiem „funkcja jest obliczalna, …
3
Jeśli abstrakcyjna maszyna może się symulować, czy to czyni Turinga kompletnym?
Na przykład w językach programowania często pisze się kompilator / interpreter X-w-X, ale na bardziej ogólnym poziomie wiele znanych systemów Turing-complete może symulować się w imponujący sposób (np. Symulując grę życia Conwaya w grze życia Conwaya ). Moje pytanie brzmi zatem: czy system jest w stanie samodzielnie przeprowadzić symulację, aby …
2
normalne zachowanie maszyn Turinga
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow …
3
Czy koncepcja maszyny Turinga pochodzi od automatów?
Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”? Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down. Zakładam, że Maszyna Turinga pochodzi od automatów, jednak nie …
2
Czy istnieje niedeterministyczny algorytm liniowego czasu dla CNF-SAT?
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema taśmami . Uważam, że istnieje NTM, który rozwiązuje CNF-SAT etapami n⋅poly(log(n))n⋅poli(log⁡(n))n \cdot \texttt{poly}(\log(n)) …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
3
Dlaczego używamy maszyn Turinga z pojedynczą taśmą ze względu na złożoność czasu?
Jak wiadomo, istnieje wiele anomolii w maszynach Turinga z pojedynczą taśmą, gdy czas jest o(n2)o(n2)o(n^2) : symulacja wielopasmowa TM, symulacja większego alfabetu taśmy za pomocą tylko {0,1,b}{0,1,b}\{0,1,b\} , konstruowania czasu, nieszczelności twierdzenia o hierarchii czasu, ... Również wyniki, takie jak DTime(o(nlgn)=RegDTime(o(nlg⁡n)=Reg\mathsf{DTime}(o(n\lg n)=\mathsf{Reg} , i bardzo specyficzne dla modelu dolne granice …
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 …
3
Kategoria „maszyn Turinga”?
Zastrzeżenie: Wiem bardzo mało o teorii złożoności. Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego: Jakie powinny być morfizmy w „kategorii” maszyn Turinga? Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to pytanie powinna idealnie dać pewne dowody i uzasadnienie …
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 …
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.