Ad Code

Responsive Advertisement

Ticker

6/recent/ticker-posts

Μη αποφασίσιμη γλώσσα: HALT

Έστω η γλώσσα:
EQ= {(M, Π)|  η μηχανή Turing Μ και το πεπερασμένο αυτόματο Π αναγνωρίζουν
την ίδια γλώσσα, δλδ, L(M)= L(Π)}.
Αποδείξτε  ότι  η EQ  είναι  μη  αποφασίσιμη. Να κάνετε την αναγωγή από τη μη
αποφασίσιμη γλώσσα: HALT = {(M,w)| η μηχανή Turing M τερματίζει με είσοδο w}.

Δημοσίευση σχολίου

0 Σχόλια