Entscheidbarkeit von Sprachen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wann ist eine Sprache L entscheidbar? |
Laut unserem Skript: Eine Sprache L ist entscheidbar, wenn es eine Turingmaschine gibt, die auf allen Eingaben stoppt und L akzeptiert.
Ich komm da nicht ganz mit. Angenommen ich habe Probleme, diese liegen alle in L. Sagen wir einfach L enthält Zahlen und mein Problem wäre: Ist diese Zahl = 5? Dann könnte die Turingmaschine meine Probleme nur entscheiden, wenn die Zahl wirklich 5 ist. Ist sie 4, endet die Turingmaschine in einem nicht akzeptierenden Zustand und wäre demnach nicht entscheidbar?
Letztlich hat sie doch aber entschieden, dass 4 != 5 ist. Warum ist das dann nicht entscheidbar?
Gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 06.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
