– Ett beslutsproblem P sägs vara semi-avgörbart (d.v.s. ha en semi-algoritm) om språket L för alla ja-instanser till P är r.e. – (Ekvivalensproblem för DFA) Med tanke på två DFA, accepterar de samma språk? Bevis: Kom ihåg Cantors argument från första föreläsningen.
När ett problem sägs vara halvavgörbart?
Halvbeslutbara problem är de för som en Turing-maskin stoppar på den inmatning som den accepterar men den kan antingen stanna eller loopa för alltid på ingången som avvisas av Turing-maskinen. Sådana problem kallas Turing Recognizable problem.
Vad är ett delvis avgörbart problem?
Definition: Ett vars associerade språk är ett rekursivt uppräknat språk. På motsvarande sätt finns det en algoritm som stoppar och matar ut 1 för varje instans som har ett "ja"-svar, men för instanser som har ett "nej"-svar är det tillåtet att antingen inte stanna eller stoppa och mata ut 0.
Är stoppproblemet delvis avgörbart?
Alan Turing bevisade 1936 att en allmän algoritm som körs på en Turing-maskin som löser stoppproblemet för alla möjliga programinmatningspar nödvändigtvis inte kan existera. Följaktligen är stoppproblemet oavgörbart för Turing-maskiner.
Varför är stoppproblemet halvt avgörbart?
Ett språk sägs vara halvavgörbart om det finns en Turing-maskin som stoppar om ett ord tillhör språket (JA-fall) och kan avvisa eller gå in i oändlighet loop om ordet inte tillhör språket (NO fall).
