BuK/IIm20/Vorlesung 6 Belkouchi

Wiki-Quelltext dieser Seite.

<language>Javascript</language>


== Seite 20 ==

<code id="608f2bb6b5b4a">
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]);
}
}
</code>

<run id="608f2bcb31f9e">
PCP();
</run>

== 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.

[[Bild:Soufiane_Aufzaehlen-1-.jpg]]

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

[[Bild:Soufiane_Entscheiden-1-.jpg]]