Décider de décidabilité est-il décidable?

Je me demande si décider de la décidabilité du problème est un problème décidable. Je suppose que non, mais après des recherches initiales, je ne trouve aucune documentation sur ce problème.

computability undecidability decision-problem synchroniser
la source

Yo, dawg, je vous ai entendu comme décidabilité alors ...

David Richerby

Votre question ne peut pas être répondue dans sa forme actuelle, comme le montrent les deux réponses qui disent essentiellement "Trivially, no" et "Trivially, yes" (avec un commentaire bonus disant "non" au "non"). Vous avez demandé si un problème est décidable mais vous n'avez pas défini ce qu'est ce problème. En particulier, quelle est l'entrée? Si vous souhaitez concevoir une machine de Turing qui vous dira si un problème est décidable, vous devez donner ce problème comme une entrée à . Mais comment fais-tu cela?

M

$M$

M

$M$

David Richerby

Compte tenu des réponses actuelles, il y a la question "Est-ce que décider de décider de la décidabilité décidable décidable?", Mais je ne vais pas la poser :-)

Mark Hurd

Réponses:

Modification majeure de mon original:

Une lecture naïve de votre question semble être, laissez être le problème $P$

Étant donné une langue, , est-elle décidable? $P=$ $L$

Ensuite, vous demandez

est-il décidable? $P$

Comme l'ont fait remarquer DW et David, la réponse est «oui», bien que nous ne sachions pas lequel des deux décisifs triviaux est le bon. Afin de cadrer votre problème afin qu'il ne soit pas aussi trivial, je suggère ceci. Tout d' abord, nous allons limiter les choses un peu en ne considérant que les langues qui sont les langues acceptées par certains TM . La raison en est que si une langue n'est acceptée par aucune MT, elle n'est pas ré (reconnaissable) et ne peut donc pas être récursive (décidable). Ensuite, nous pouvons refondre comme $L(M)$ $M$ $P$

Etant donné une description, d'un TM, est décidable? $P'=$ $\langle M\rangle$ $M$ $L(M)$

Maintenant, est un langage de descriptions TM, plutôt qu'un langage de langues comme semblait l'être (sous une interprétation généreuse), et il est maintenant parfaitement raisonnable de se demander si le langage est décidable. Selon cette interprétation, la langue composé de descriptions TM ne sont pas décidable. C'est une conséquence facile du théorème de Rice . Alors maintenant, nous avons deux réponses: mon "non" et DW "oui", selon l'interprétation. $P'$ $P$ $P'$

{⟨ M ⟩ ∣ M est une MT et L (M) est décidable}

$\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}$

Rick Decker
la source

Je vous remercie! La compréhension, au moins superficielle, des deux réponses m'a donné l'information que je cherchais, qui est approximativement: "Pouvons-nous créer une machine qui peut décider ce qu'elle peut et ne peut pas décider en général?" (Pas une bonne formulation, je sais, mais je ne peux pas penser à une meilleure formulation.) Très utile, surtout que vous reconnaissez les deux interprétations.

synchronisation

J'ai pensé que montrer que pour chaque problème décidable il y avait un certificat (algorithme avec une preuve) et pour chaque problème indécidable il y avait aussi un certificat (réduction du problème indécidable) était suffisant.

rus9384

Comme nous l'avons vu dans les différentes réponses, une partie de la réponse consiste à formuler le bon problème.

En 1985, Joost Engelfriet a écrit "La non-calculabilité de la calculabilité" (Bulletin de l'EATCS numéro 26, juin 1985, pages 36-39) comme réponse à une question posée par un étudiant intelligent. Malheureusement, le BEATCS était à l'époque uniquement papier et l'article n'a laissé aucune trace électronique.

$\Psi$ $F(m,n)$ $f:\Bbb N \to \Bbb N$ $m,n\in \Bbb N$ $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ $\underline m$ $m$

Je cite:

$\Phi$ $\Bbb N \to \Bbb N$ $f$ $f$

La partie amusante est dans l'observation suivante faite dans le document:

$\Phi$

Hendrik Jan
la source

Oui. C'est toujours décidable.

Pour tout problème P, soit Q le problème de déterminer si P est décidable ou non. Je prétends que Q est décidable. Voici pourquoi. Tautologiquement, soit P est décidable, soit il ne l'est pas. Ainsi, l'un des deux programmes est correct: (1) print "yup P is decidable"ou (2) print "nope P is not decidable". Il pourrait être non trivial de déterminer lequel de ces deux programmes est correct, l'un d'eux est correct, donc un décideur pour Q existe sûrement . Par conséquent, le problème Q est décidable.

Cela rappelle la question classique suivante: est-il décidable de dire si la conjecture de Collatz est vraie? La réponse est oui. Cela peut sembler étrange, car personne ne sait si la conjecture de Collatz est vraie (c'est un problème ouvert célèbre). Cependant, ce que nous savons, c'est que la conjecture de Collatz est vraie ou non. Dans le premier cas, le programme print "yup it's true"est déterminant. Dans ce dernier cas, le programme print "nope it's not true"est déterminant. Nous ne savons pas lequel est un décideur valide, mais cela suffit pour prouver qu'il existe un décideur valide. Par conséquent, le problème est décidable.

DW
la source

Je pense que l'interprétation de la question par Ricky Decker est supérieure. Étant donné l'encodage d'un problème, décidez si le problème est décidable.

Yuval Filmus

@YuvalFilmus, OK, c'est raisonnable. Avez-vous un encodage fini pour les problèmes (c.-à-d. Les langues) qui vous semble raisonnable et ne rend pas le problème trivial? L'encodage fini naturel pour une langue est comme une machine de Turing qui reconnaît cette langue, mais qui rend le problème trivial, comme l'illustre votre commentaire sur la réponse de Ricky Decker. Nous aurions donc besoin d'un autre encodage raisonnable, qui ne souffre pas de ce genre de problème. Avez-vous des suggestions à ce sujet?

Vous pouvez utiliser la logique du premier ordre dans un langage approprié. Ou l'entrée pourrait être une machine en 0 '(par exemple), c'est-à-dire une machine de Turing avec accès à un oracle d'arrêt.

Yuval Filmus

Selon le théorème de Rice, nous savons même que décider que R dans l'univers RE est indécidable. N'est-ce pas suffisant? (Toutes les MT ne sont pas des décisions.)

Raphael

Je vous remercie! Même si ce n'était pas l'interprétation que je voulais, cela m'a aidé à comprendre pourquoi la question que je posais n'était peut-être pas suffisamment bien formulée pour refléter mes intentions.

synchronisation