Berechenbarkeitstheorie/Entscheidbarkeit und Aufzählbarkeit

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Aufzählbarkeit==

<code id="4f71911f5966d">
(define tree-1 '(1 (2 (4) (5)) (3 (6) (7))))

(define node? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 3))))

(define leaf? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 1))))


(define tiefe (lambda (tree)
                (cond
                  [(leaf? tree) (list (car tree))]
                  [else 
                   (let( [element (car tree)]
                         [left (cadr tree)]
                         [right (caddr tree)])
                     (cons element
                           (append (tiefe left)
                                   (tiefe right))))])))
</code>
<run id="4f71911f5972a">(display tree-1)</run>


Beispiel: Wörter der Länge 3 über $\{a,b\}^*$

Die zu charakterisierende Menge ist eine endliche, denn es gibt nur $2^3=8$ solche Wörter.

<code id="4f6cafece05e6">
(define chi-laenge3
  (lambda (w)
    (if (member w '("aaa" "aab" "aba" "baa" "abb" "bab" "bba" "bbb"))
      #t
      #f))) 
</code>
<run id="4f6cafece065c">(chi-laenge3 "abb")</run>


Beispiel: Wörter über $\{a,b\}^*$, die mit $a$ beginnen. 

<code id="4f6ca9bc8928d">
(define chi-a
  (lambda (w)
    (char=? (string-ref w 0) #\a)))
</code> 
<run id="4f6ca9bc89383">
(chi-a "ababaab")
</run>

Die Menge der Primzahlen ist aufzählbar unendlich:
<code id="4f71666af239c" hidden>
(define prim?
  (lambda (n)
    (letrec
        ((helfer
          (lambda (t)
            (cond
              ((> t (sqrt n)) #t)
              ((= (remainder n t) 0) #f)
              (else
               (helfer (+ t 2)))))))
      (cond
        ((= n 1) #f)
        ((= n 2) #t)
        ((= (remainder n 2) 0) #f)
        (else
         (helfer 3))))))
</code>
<run id="4f71666af2ed9">(prim? 31)</run>
<code id="4f71666af2b1e">
(define f 
  (lambda (n)
    (if (prim? n)
      n
      2)))
</code>
<run id="4f71666af3428">(f 31)</run>