Vorlesung 6 Belkouchi

Aus ProgrammingWiki

Archivierte Version vom 2021-05-02T22:43:47+00:00. Aktuelle Version

Seite 20

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])
        write("PCP Lösung:"+listIndex[i]);
}

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.

Vorlesung 6 Belkouchi

Seite 20

Seite 30

Suche