Pytania otagowane jako halting-problem

Biorąc pod uwagę program i dane wejściowe, czy zatrzymuje się, czy działa na zawsze?

3
Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem płytek są często nierozstrzygalne (np. Czy ta płytka poliomino ma jakiś prostokąt?), …
1
Problem zatrzymania, niepoliczalne zbiory: wspólny dowód matematyczny?
Wiadomo, że z policzalnym zestawem algorytmów (charakteryzujących się liczbą Gödla) nie możemy obliczyć (zbudować algorytmu binarnego, który sprawdza przynależność) wszystkich podzbiorów N. Dowód można podsumować w następujący sposób: jeśli moglibyśmy, to zestaw wszystkich podzbiorów N byłby policzalny (moglibyśmy powiązać z każdym podzbiorem liczbę Gödla algorytmu, który go oblicza). Ponieważ jest …
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, …
2
Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?
Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …
1
Jak dobry może być detektor zatrzymania?
Czy istnieje Maszyna Turinga, która może zadecydować, czy prawie wszystkie inne Maszyny Turinga zatrzymają się? Załóżmy, że mamy jakieś wyliczenie maszyn Turinga i pewne pojęcie o „rozmiarze” zbioru liczb naturalnych, a my definiujemy:N →{ Mja}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥ ⋅∥‖⋅‖\| \cdot \| fa( i ) = ∥ { n : Mja nie …
1
Czy w teorii typów istnieje dobre pojęcie o braku terminacji i zatrzymaniu dowodów?
Konstruktywna teoria typów z jej podstawową interpretacją w ramach korespondencji curry-howard składa się wyłącznie z całkowitych, obliczalnych funkcji. W literaturze niektórzy mówili o stosowaniu „teorii typów obliczeniowych” w celu przedstawienia nieterminacji w programach funkcjonalnych, ale w artykułach, na które się natknąłem, nie wydaje się to być główną motywacją dla teorii …
1
Jakie jest odniesienie do pierwszego twierdzenia Gödela o niekompletności opartego na nierozstrzygalności problemu zatrzymania?
Słabsza forma pierwszego twierdzenia Gödela o niekompletności, którego bezpośrednie dowody są w sposób Gödela długotrwałe, zaangażowane, aw niektórych miejscach raczej sprzeczne z intuicją, ma prosty i intuicyjny dowód oparty na nierozstrzygalności problemu zatrzymania - patrz na przykład https: / /en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof Kto pierwszy zaproponował ten dowód iw jakim artykule lub książce …
2
Maszyny Turinga, których zakończenie jest niemożliwe do udowodnienia?
Mam naiwne pytanie: czy istnieje maszyna Turinga, której zakończenie jest prawdziwe, ale której nie da się udowodnić żadną naturalną, spójną i skończoną aksjomatyczną teorią? Proszę o zwykły dowód istnienia, a nie o konkretny przykład. Może to mieć związek z analizą porządkową . Rzeczywiście, dla maszyny Turinga możemy zdefiniować jako najmniejszy …
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.