Ja, skillnaden mellan avgörande och igenkännbara språk är helt tydlig. Skillnaden ligger i beteendet hos en Turing Machine (TM) som försöker bestämma medlemskap:
* avgörande språk (rekursivt språk): Ett språk L är avgörande om det finns en Turing -maskin som för * varje * ingångssträng W, stoppar och korrekt svarar "Ja" om w ∈ L och "Nej" om W ∉ L. Detta betyder att TM alltid stoppar, oavsett om ingången är på språket eller inte.
* igenkännligt språk (rekursivt ärligt språk): Ett språk L är igenkännligt om det finns en Turing -maskin som för * varje * inmatningssträng W, stoppar och svarar "Ja" om w ∈ L. Men om W ∉ L kan TM stoppa och svara "Nej" eller så kan det gå för alltid (slingan på obestämd tid). Nyckeln är att den * alltid * ger rätt svar ("ja") om strängen är på språket; Det är bara tillåtet att vara icke-deterministiskt eller misslyckas med att ge ett svar när strängen är * inte * på språket.
I enklare termer:
* Avgörbar: TM ger alltid ett definitivt svar (ja eller nej) i begränsad tid.
* igenkänd: TM ger ett "ja" -svar i begränsad tid om ingången finns på språket, men kanske inte ger ett svar (genom att looping för evigt) om ingången inte finns på språket.
Varje avgörande språk är också igenkänd. Men konversationen är inte sant; Det finns igenkännliga språk som inte är avgörande. Stoppproblemet är ett klassiskt exempel på ett språk som är igenkännligt men inte avgörande. En TM kan byggas som känner igen strängar som representerar att stoppa Turing -maskiner (det simulerar maskinen och svarar "Ja" om den stoppar), men ingen TM kan avgöra om en godtycklig Turing -maskin kommer att stoppa på en given ingång (eftersom det skulle lösa själva stoppproblemet).
Skillnaden beror på huruvida TM garanterar uppsägning för alla ingångar (avgörande) eller bara garanterar ett "ja" -svar i begränsad tid för ingångar på språket (igenkännbart). Skillnaden är grundläggande i beräkningsteorin.
