Aiutami a capire questo problema della macchina di tentazione riguardante $ A_ {TM} $

Question

Sono una fisica / C.S. Studente e hanno lottato con questo particolare problema per alcuni giorni ora. Quindi il compito è il seguente:

---

.

Considera le seguenti lingue:

$ \ hspace {20pt} l_1={\ Langle m \ Rangle \, | \, L (m)= a_ {tm} \} \\ \ hspace {20pt} l_2={\ Langle m \ Rangle \, | \, L (m)=overline {a_ {tm}}}} $

sono questi decidabili? Dimostra la tua decisione.

$ a_ {tm} $ è definito come $ \ {\ Langle m, w \ Rangle \, | \, \ text {m è un tm e m accetti w} \} $

---

.

Quindi prima di prima cosa sto cercando di capire la prima lingua $ l_1 $ . Cosa significherebbe esattamente per $ l_1 $ per essere decidabile? Capisco perché $ a_ {tm} $ non è decidabile, ma quale sarebbe un TM che decide $ l_1 $ In realtà?

Ho sento di conoscere già la soluzione al secondo problema, ma vorrei sapere se il mio istinto di intestino è giusto. Quindi da $ \ Overline {A_ {TM}} $ non è in forma-riconoscibile significa che $ m $ Con $ L (M)=Overline {A_ {TM}} $ non esiste / è vuoto. Quindi $ l_2=vuoto $ e questo è facilmente decidabile.

Answer 1

Risolvere la lingua $ l_1 $ significa sapere per ogni TM se è semi-decidere la $ A_ {TM} $ problema.

Il tuo istinto è giusto - è vuoto e quindi decidabile. Se non è stato vuoto per caso, poi con il teorema del riso non sarebbe stato decidabile