BuK/IIm14/Studenten/s3roried

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
<language>Javascript</language>
<language>Javascript</language>
= Kapitel 3 =

== Anzahl berechenbarer charakteristischer Funktionen ==
Die Wortmenge $A*$ ist ''abzählbar unendlich''. Für jedes Wort aus $A*$ gibt es eine Funktion $\chi$, welche $true$ oder $false$ zurückgibt.

Von der Wortmenge $A*$ wird nun die Potenzmenge $P(A*)$ erzeugt, welche überabzählbar unendlich ist.
Für jedes Element von $P$ kann man nun ebenfalls eine eine Funktion $\chi$ erzeugen.
Diese Mengen $P(P(A*))$ haben ebenfalls ''überabzählbar'' unendlich viele Funktionen $\chi$.

== Aufzählbarkeit gerader Zahlen ==

Zu zeigen ist, dass die Menge der geraden Zahlen $G$ aufzählbar ist.
Es gilt eine ''Aufzählprozedur'' $g:\N \mapsto G$ zu finden. $g$ muss ''berechenbar'' und ''surjektiv'' sein.

Wenn es eine solche Funktion gibt, dann ist $G$ ''aufzählbar''.

$g(n)=2k$ wobei $n,k\in \N$


Algorithmus:
<code id="552e5cea2ba3e">
function g(n) {
    return 2*n;
}
</code>
<run id="552e5cea2bab7" >
g(3);
</run>

== Aufzählbarkeit von Primzahlen ==

Zu zeigen ist, dass die Menge der Primzahlen $P$ aufzählbar ist.
Es gilt eine ''Aufzählprozedur'' $p:\N \mapsto P$ zu finden. $p$ muss ''berechenbar'' und ''surjektiv'' sein.

Wenn es eine solche Funktion gibt, dann ist $P$ ''aufzählbar''.

$p(n) =  \left\{\begin{array}{cc}n; wenn \ prime?(n)\\
2; sonst\\
\end{array}\right.
$

Algorithmus:
<code id="552e6f2a80094" >
function kleinsterTeiler (n){
  return findeTeiler(2,n);
}

function findeTeiler(a,n){
  if((2 < a) && (a < Math.sqrt(n))){
    teilt(a,n)
  } else {
    findeTeiler(a+1,n)}
} 
    
function teilt(a,b){
  return b % a;
}

function primzahl(n){
  return n==kleinsterTeiler(n);
}
function nZuPrim(n){
  if(primzahl(n)){return n;
  } else {
  return 2;}
}
</code>
<run id="552e6f2a8011c"  >
// too much recusrion ... wo ist der fehler?
nZuPrim(3);
</run>

<language>Javascript</language>
<language>Javascript</language>
==Aufbauprozedur für A*==
Ausgehend von der leeren Menge wird an diese ein Element des Alphabets angefügt und es entstehen entsprechend viele neue Mengen. Diese Prozedur kann nun beliebig oft wiederholt werden.
<code id="552e79a0c8601">
function nZuAStern(n, alphabet){
if (n <= alphabet.length){
    if(n=0){
       return ['empty'];
    } else {
       return alphabet[n]}
    };
var aStern = alphabet;
var alphabetCounter = 0;
var counter = 0;
while (n > 0)
{
var aSlength=aStern.length;
for(i=0;i<aSlength;i++){
    aStern.push(aStern[i].concat(alphabet[alphabetCounter]));
    if(counter >= alphabet.length-1){
       alphabetCounter = 0;
    } else {alphabetCounter ++;}
//counter mit alphabet abgleichen/teilen
}
n--;
}
 return aStern;
}
</code>
<run id="552e79a0c8692">
nZuAStern(10,['a','b','c']);
</run>