Synthèse du programme, décidabilité et problème d'arrêt

Je lisais une réponse à une question récente, et une sorte de pensée étrange et éphémère m'est venue à l'esprit. Ma demande pourrait trahir soit que mes côtelettes théoriques manquent sérieusement (surtout vrai) ou qu'il est tout simplement trop tôt pour moi de lire ce site. Maintenant, avec l'avis de non-responsabilité ...

C'est un résultat bien connu de la théorie de calculabilité que le problème d'arrêt ne peut pas être décidé pour les MT. Cependant, cela n'exclut pas la possibilité qu'il existe des machines capables de résoudre le problème d'arrêt pour certaines classes de machines (mais pas toutes).

Considérez l'ensemble de tous les problèmes décidables. Pour chaque problème, il existe une infinité de MT qui décident de cette langue. Les éléments suivants pourraient-ils être possibles

Il existe une MT qui décide du problème d'arrêt pour un sous-ensemble de machines de Turing; et $S$
Tous les problèmes décidables sont décidés par au moins une machine de Turing en ? $S$

Bien sûr, trouver la machine de Turing en peut ne pas être calculable en soi; mais nous ignorons ce problème. $S$

EDIT: Sur la base de la réponse de Shaull ci-dessous, il semble que (a) cette idée est trop mal spécifiée pour être significative ou (b) ma tentative précédente n'était pas tout à fait sur la marque. Comme j'essaie d'élaborer dans les commentaires à la réponse de Shaull, mon intention est pas que nous sommes garantis que la TM d'entrée est en . Ce que je voulais vraiment dire par ma question, c'est s'il pouvait exister un tel , de telle sorte que l'appartenance au soit un problème décidable . Le programme pour résoudre le problème d'arrêt de écrirait, vraisemblablement, une "entrée invalide" sur la bande ou quelque chose quand on lui donne une entrée qu'il reconnaît comme n'étant pas en $S$ $S$ $S$ $S$ $S$ . Quand je le formule comme ça, je ne sais pas si cela nous permet de résoudre le problème d'arrêt ou non, ou si le théorème de Rice s'applique (la décidabilité est-elle une propriété sémantique d'un langage par rapport au théorème de Rice?)

turing-machines undecidability halting-problem Patrick87
la source

pense qu'il y a une question légitime / significative aux limites de la théorie qui se cache quelque part ici, mais pas dans la forme actuelle, néanmoins +1 pour avoir essayé [et cet avertissement au début est surprenant compte tenu de votre statut de représentant / modérateur] ... peut-être que c'est la question que vous lisiez? algorithme pour résoudre le problème d'arrêt des turings

vzn

peut-être une autre façon de formuler la question, je ne sais pas si c'était l'intention (ce qui la rend très avancée). considérer tous les "algorithmes quasi-possibles" possibles et leurs ensembles reconnus associés

. [Voir autre question pour les defns]. l'union de tous ces ensembles reconnus

égale à l'ensemble de toutes les MT récursives / décidables?

S_{n}

$S_n$

S_{n}

$S_n$

vzn

Je pense qu'il peut y avoir un problème avec la formulation du problème.

Considérons l'ensemble est un décideur de son langage . Le problème d'arrêt est décidable pour cet ensemble (c'est-à-dire, si on nous promet que l'entrée est dans cet ensemble). En fait, il est trivial (les machines arrêtent toujours). $S=\{M: M$ $\}$ $S$

En outre, clairement toutes les langues décidable est en . $S$

EDIT: Sur la base des changements dans la question - en effet, l'appartenance à serait indécidable: si contient une machine pour chaque langue décidable, alors . Ainsi, par le théorème de Rice, si est décidable alors contient toutes les machines, mais le problème est indécidable sur arrêt . $S$ $S$ $S\neq \emptyset$ $S$ $S$ $S$

Shaull
la source

En d' autres termes,

répond trivialement à la question positivement.

S = {⟨ A ⟩ ∣ \forall x . A (x) ↓, L (A) \in R}

$S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$

Raphael

@Raphael - non, car si

, cela n'implique pas que

est un décideur. C'est pourquoi nous prenons explicitement les décisions.

L (A) \in R

$L(A)\in R$

A

$A$

Shaull

Ah, c'est vrai. Correction du commentaire.

Raphael

+1 Je ne suis pas sûr d'avoir clairement communiqué mon sens. Ce que je voulais demander est de savoir s'il est possible qu'un tel

existe, et nous pouvons vérifier un arbitraire TM pour voir si elle est en

. On ne sait pas a priori que c'est en

; juste que

est formulé de telle manière que nous pouvons vérifier. En d'autres termes, est-il possible qu'il existe un

tel que l'appartenance à

soit décidable? De plus, votre dernière phrase est quelque peu déroutante;

est un ensemble de machines de Turing (enfin, leurs représentations); pas des langues que les MT décident ... mais je pense que je sais ce que vous voulez dire.

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

Patrick87

(ps Désolé de vous tromper de nom dans mes modifications. Il est trop tôt pour moi pour faire CS.SE commence à apparaître de plus en plus probable)

Patrick87

Synthèse du programme, décidabilité et problème d'arrêt

Réponses: