Podjęzyk nie jest rozpoznawalny przez Turinga, czy może być?

10

Niech A i B będą językami z A ⊆ B, a B jest rozpoznawalny przez Turinga. Czy A może nie być rozpoznawalny przez Turinga? Jeśli tak, czy jest jakiś przykład?

computability gfe
źródło

18

Jest to coś, co dezorientuje wielu uczniów. Chodzi o to, że podzbiór innego języka nie implikuje wiele na temat ich trudności obliczeniowych. Zawsze możesz wziąć pod uwagę trywialny język i a każdy inny język znajduje się między nimi. $\emptyset$ $\Sigma^*$

Dlatego sama wiedza o tym, że język zawiera lub zawiera się w języku łatwym do obliczenia, nie mówi nic o trudnościach z jego obliczeniem.

Kaveh
źródło

Ale nie mogę znaleźć żadnego podzestawu języka Σ ∗, który nie byłby rozpoznawany przez Turinga.

gfe

3

@Wilhelm, weź każdy język, który nie jest rozpoznawany przez Turinga, i będzie działać.

Kaveh

Rozumiem, więc mogę użyć problemu zatrzymania, aby udowodnić, że istnieje taki język.

gfe

@Wilhelm, tak. :)

Kaveh

1

Gdy język rozpoznawalny przez Turinga nie jest rozstrzygalny, oznacza to, że nie jest on rozpoznawalny przez Turinga (innymi słowy: nie jest rozpoznawalny). Ponieważ jest doskonale poprawnym podzbiorem , potwierdza to fakt, że dla języka którym jest rozpoznawalny przez Turinga, może nie być. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Szlifierka
źródło

Myślę, że odpowiedź Kaveha jest lepsza i do rzeczy. Każdy język jest podzbiorem

i wiemy, że

jest rozstrzygalne i że istnieją arbitralnie twarde języki.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

Właśnie to próbowałem wyjaśnić, ponieważ

może być dowolnym językiem, ponieważ

automatycznie się utrzymuje. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander,

-3

Twoja dyskusja mnie pomyliła :(

„Czy można nie rozpoznać Turinga?”

Czuję, że A jest zawsze rozpoznawalne przez Turinga . Oto moje myślenie

Ponieważ B jest rozpoznawalny przez Turinga => Istnieje pewna baza TM, która akceptuje wszystkie słowa języka B => Istnieje baza TM, która akceptuje (wszystkie słowa języka A + niektóre inne słowa) => Istnieje baza TM, która akceptuje wszystkie słowa języka A => A jest rozpoznawalny przez Turinga.

Czy to źle? Czy może istnieć jakikolwiek przypadek, w którym A nie jest TRL, a B jest TRL. Uprzejma pomoc

bongubj
źródło

1

Tak, to jest złe: osoba akceptująca język nie może akceptować żadnych słów oprócz tych w tym języku.

reinierpost

Nie publikuj pytań uzupełniających jako odpowiedzi. Skorzystaj z komentarzy (po tym, jak udowodnisz systemowi, że jesteś godny zaufania) lub utwórz nowy post, jeśli nowe pytanie różni się znacznie (nie w tym przypadku).

Raphael

-4

W tym przypadku A nie może być rozpoznawalny przez Turinga. Weź to jako przykład:

język B to połączenie języka tr (C) i języka innego niż tr (A). możesz stworzyć maszynę Turinga, która rozpoznaje B. A nie jest tr, a A ⊆ B.

czy to prawda? nie wiem czy to jest .. więc .. =)

Philip A.
źródło

3

C \in R E

$C\in RE$

A \notin R E

$A\notin RE$

C = \emptyset

$C=\emptyset$

A

$A$

B = A \cup C

$B=A \cup C$

Podjęzyk nie jest rozpoznawalny przez Turinga, czy może być?

Odpowiedzi: