Kann

8

Ich versuche mir die Berechenbarkeitstheorie mit einem Lehrbuch beizubringen. Nach meinem Buch ist eine Funktion über einem Alphabet ist nur in der Sprache berechenbarA = { a , b , c , d , e , f , g , h , i , j , k , l , m , n , o , p , q , r , s , t , u , v , w , x , y , z }fA={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

L={s#jσ:sA,σA, the j'th symbol of f(s) is σ}

ist entscheidbar. Warum ist das so? Könnte eine Funktion nicht berechenbar sein, selbst wenn entscheidbar ist?fL

Ava Petrofsky
quelle

Antworten:

6

Wenn entscheidbar ist, können Sie seinen Entscheider verwenden, um zu berechnen : Führen Sie für das erste Symbol von den Entscheider auf der Eingabe für jedes . Für einen von ihnen antwortet der Entscheider mit JA - dies ist der erste Buchstabe in .Lff(s)s#xxAf(s)

Fahren Sie damit fort (z. B. für den zweiten Buchstaben, entscheiden Sie, ob usw. ist), und geben Sie Buchstabe für Buchstabe an, bis der Entscheider für alle NEIN antwortet. , was bedeutet, dass Sie das Ende von .s##xLf(s)xAf(s)

Wenn also entscheidbar ist, ist berechenbar. Wenn umgekehrt nicht berechenbar ist, kann es nicht sein, dass entscheidbar ist.LffL

Ran G.
quelle