Vorlesung 6 Belkouchi

Aus ProgrammingWiki

Seite 20

function PCP(){ let instanz = [["1", "101"], ["10", "00"], ["011", "11"]]; let listIndex=new Array(); let x_word=new Array(); let y_word=new Array(); for(var i=0;i<3;i++){ for(var j=0;j<3;j++){ for(var z=0;z<3;z++){ listIndex.push(new Array(i,j,z)); for(var a=0;a<3;a++){ listIndex.push(new Array(i,j,z,a)); } } } } listIndex.forEach(function(item){ var strx=""; var stry=""; item.forEach(function(index){ strx=strx+instanz[index][0]; stry=stry+instanz[index][1]; }); x_word.push(strx); y_word.push(stry); }); for(var i=0;i<listIndex.length;i++){ if (x_word[i] == y_word[i]) return("PCP Lösung:"+listIndex[i]); } }

PCP();

ausführen

Seite 30

Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.

Turing-aufzählbar , wenn alle Worte von A auf einem ihrer Bänder ausgibt. Dabei dürfen Worte von M auch mehrfach ausgegeben werden.

M heißt Turing-entscheidbar, wenn bei Eingabe eines Wortes w feststellt, ob w zu A gehört oder nicht.