Réduction de A_LBA à E_LBA

Question

J'ai une assez intéressante à méditer et je serais ravi si je pouvais obtenir une réponse pour cela. Nous avons discuté de la question d'aujourd'hui la réduction de la cartographie dans mon cours de théorie informatique et je me demandais pourquoi cette réduction ne peut pas exister, A_ $ {LBA} \ leq_ {m} E_ {LBA} $, puisque les deux sont des automates linéaires liés (LBA). Je réalise que $ E_ {LBA} $ est indécidable, $ A_ {LBA} $ est décidable, et la preuve normale utilise A_ $ {tm} $, ou $ E_ {TM} $, pour prouver l'undecidibility de $ E_ { } $ LBA. Je suis juste curieux de savoir pourquoi la preuve utilise un TM pour prouver un LBA. Mais, mon professeur ne pouvait pas trouver une solution à ma confusion. Je me demandais est-ce possible, si oui, pourquoi ou pourquoi pas.

Définitions:

A_ $ {} = LBA \ {\ langle M, w \ rangle \ mid \ texte {$ M $ est un automate lié linéaire qui accepte la chaîne $ w $} \} $

$ E_ {} = LBA \ {\ langle M \ rangle \ mid \ texte {M $ est un automate lié linéaire avec $ L (M) = \ emptyset $} \} $

$ A_ {TM} $ et $ E_ {TM} $ sont les problèmes équivalents pour les machines de Turing.

Answer 1

Vous avez votre carte dans le mauvais sens. En l'état actuel, ce serait une réduction d'un problème décidable à un problème indécidable. Il est certainement possible (voir ci-dessous), mais il ne nous dit rien.

Rappelons que si $ A \ leq_ {m} B $, puis un algorithme de résolution $ B $ (ou décider de l'adhésion dans ce cas) peut être utilisé pour résoudre $ A $ (adhésion à décider $ A $). Ainsi, la réduction que vous regardez nous disait que tout decider pour $ E_ {} $ pourrait LBA être utilisé pour décider $ A_ {} $ LBA. Il nous arrive de savoir que $ E_ {} $ est LBA indécidable, mais cela ne l'empêche pas qu'il y ait un peu pour decider $ A_ {} $ qui LBA ne décide pas E_ $ {} $ LBA.

En fait, la réduction que A_ {LBA} $, ne peut pas exister est $ E_ {LBA} \ leq_ la {m} car cela impliquerait que nous pourrions décider $ E_ {LBA} $, que nous savons que nous pouvons « t.

Pour la deuxième partie, la preuve (ou plutôt, l'une des preuves possibles) que $ E_ {LBA} $ est indécidable est par la construction de la cartographie $ A_ {TM} \ leq_ {m} E_ {LBA} $, donc à nouveau un decider pour $ E_ {LBA} $ nous donnerait un decider pour $ A_ {TM} $, mais nous savons déjà que A_ $ {tm} $ est indécidable donc $ E_ {LBA} $ doit également être indécidable.

pourquoi la preuve utilise une langue qui implique des machines pour montrer Turing quelque chose sur automates linéaire lié, il est parce que cela fonctionne.

une réduction

$ A_ {} $ est LBA décidable, nous pouvons prendre l'entrée $ M $ LBA et string $ w $, et exécutez le decider sur $ \ langle M, w \ rangle $. Si elle accepte, nous dressons la carte ce à un $ M_ {LBA rej} $ qui rejette immédiatement. Si les rejets de Decider, nous dressons la carte à un $ M_ {LBA selon} $ qui accepte immédiatement. Ainsi $ M_ {acc} $ accepte toutes les entrées et ne sont pas en $ E_ {} $ LBA et $ M_ {rej} $ rejette toutes les entrées et est en $ E_ {} $ LBA.

Note bien sûr que cette réduction est dans un sens trivial, et le sous-ensemble de $ E_ {} $ il LBA cartes à est finie et donc décidable (même régulière!).

Une autre perspective

Étant donné deux langues $ A $ et $ B $ tel que $ A \ leq_ {m} B $, il y a deux choses fondamentales (utiles) nous peut pouvoir dire:

• Si $ B $ est décidable puis $ A $ est également décidable.
• Si $ A $ est indécidable puis $ B $ est indécidable.

Dans notre cas $ A $ est décidable, et $ B $ est indécidable, qui correspond à aucune de ces possibilités, de sorte que la réduction de $ A_ {} LBA \ leq_ {m} {E_} $ ne LBA nous dit rien sur l'indécidabilité soit.