Pytania otagowane jako halting-problem

Pytania dotyczące problemu Halting, który decyduje o tym, czy dany program zatrzyma się na danym wejściu.

12
Dlaczego tak naprawdę problem zatrzymania jest tak ważny?
Nie rozumiem, dlaczego problem zatrzymania jest tak często wykorzystywany do odrzucenia możliwości ustalenia, czy program się zatrzymuje. Wikipedia [artykuł] [1] poprawnie wyjaśnia, że ​​deterministyczna maszyna ze skończoną pamięcią zatrzyma lub powtórzy poprzedni stan. Możesz użyć algorytmu, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności …
5
Czy istnieje jakikolwiek konkretny związek między twierdzeniem o niekompletności Gödla, problemem zatrzymania a uniwersalnymi maszynami Turinga?
Zawsze myślałem niejasno, że odpowiedź na powyższe pytanie była twierdząca w następujący sposób. Twierdzenie Gödela o niekompletności i nierozstrzygalność problemu zatrzymania są zarówno negatywnymi wynikami rozstrzygalności, jak i ustalonymi na podstawie przekątnych argumentów (w latach 30. XX wieku), więc muszą być jakoś dwoma sposobami spojrzenia na te same sprawy. Pomyślałem, …
10
Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?
Wiemy, że problem zatrzymania (na maszynach Turinga) jest nierozstrzygalny dla maszyn Turinga. Czy są jakieś badania nad tym, jak dobrze ludzki umysł może poradzić sobie z tym problemem, być może wspomagane przez maszyny Turinga lub komputery ogólnego przeznaczenia? Uwaga : Oczywiście, w ścisłym tego słowa znaczeniu, zawsze możesz powiedzieć „nie”, …
7
Czy istnieje związek między problemem zatrzymania a entropią termodynamiczną?
Alan Turing zaproponował model maszyny (Maszyna Turinga, TM), który oblicza (liczby, funkcje itp.) I udowodnił twierdzenie Haltinga . TM to abstrakcyjna koncepcja maszyny (lub silnika, jeśli chcesz). Twierdzenie Haltinga jest wynikiem niemożliwości. Silnik Carnota (CE) to abstrakcyjna koncepcja silnika cieplnego, a Carnot udowodnił twierdzenie Carnota , kolejny wynik niemożliwości związany …
7
Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego problemu. W książce dowód wygląda następująco: „załóżmy, że MHMHM_H …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
4
Czy problem zatrzymania jest rozstrzygalny dla czystych programów na idealnym komputerze?
Dość proste jest zrozumienie, dlaczego problem zatrzymania jest nierozstrzygalny w przypadku nieczystych programów (tj. Tych, które mają operacje we / wy i / lub stany zależne od stanu globalnego maszyny); ale intuicyjnie wydaje się, że zatrzymanie czystego programu na idealnym komputerze byłoby rozstrzygalne np. poprzez analizę statyczną. Czy tak jest …
1
Czy można udowodnić nierozstrzygalność problemu zatrzymania w Coq?
Oglądałem „ Pięć etapów akceptacji konstruktywnej matematyki ” Andreja Bauera i mówi on, że istnieją dwa rodzaje dowodów sprzeczności (lub dwie rzeczy, które matematycy nazywają dowodem sprzeczności): Załóżmy, że jest fałszywe ... bla bla bla, sprzeczność. Dlatego jest prawdziwe.P.P.PP.P.P Załóżmy, że jest prawdą ... bla bla bla, sprzeczność. Dlatego P …
6
Algorytm rozwiązywania „problemu zatrzymania” Turinga
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . „Alan Turing udowodnił w 1936 r., Że nie może istnieć ogólny algorytm rozwiązania problemu zatrzymania dla wszystkich możliwych par danych wejściowych programu” Czy mogę znaleźć ogólny …
5
Czy problem zatrzymania można „rozwiązać”, przechodząc do opisu obliczeń wyższego poziomu?
Niedawno usłyszałem ciekawą analogię, która stwierdza, że ​​dowód Turinga na nierozstrzygalność problemu zatrzymania jest bardzo podobny do paradoksu fryzjerskiego Russella. Zastanawiałem się więc: matematycy w końcu zdołali ujednolicić teorię zbiorów, przechodząc od naiwnego sformułowania pola przez Cantora do bardziej złożonego systemu aksjomatów (teoria zbiorów ZFC), dokonując po drodze istotnych wyłączeń …
4
Czy środowisko wykonawcze może wykryć nieskończoną pętlę?
Czy środowisko wykonawcze może wykryć nieskończone pętle, a następnie zatrzymać powiązany proces, czy też wdrożenie takiej logiki byłoby równoznaczne z rozwiązaniem problemu zatrzymania? Na potrzeby tego pytania definiuję „nieskończoną pętlę”, która oznacza serię instrukcji i powiązanych początkowych danych stosu / sterty, które po uruchomieniu zwracają proces do dokładnie tego samego …
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.