BuK/IIm11/Studenten/sichochm

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Kreativaufgabe: Gödelisierung und $\mu$-rekursive Funktionen'''
<code id="508d8bc6ef6c1" hidden>
(define get-elem
  (lambda (set index)
    (if (= index 1)
      (car set)
      (get-elem (cdr set) (- index 1)))))

;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define word-number
  (lambda (cardinal-number letter-count)
    (if (= letter-count 0)
      0
      (+
        (pow cardinal-number letter-count)
        (word-number cardinal-number (- letter-count 1))))))
    
(define fCreator
  (lambda (set)
    (lambda (index)
      (if (= index 0)
        ""
        (let((cardinalNumber (cardinalNumber testSet))
            (lettersRemaining (calculateWordSize testSet index)))
          (createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining))))))



(define cardinalNumber
  (lambda (set)
    (if (null? set)
      0
      (+ 1 (cardinalNumber (cdr set))))))

(define calculateWordSize
  (lambda (set index)
    (letrec ((calculateWordSizeReal
      (lambda (cardinalNumber index sum exp)
        (if (>= sum index)
          0
          (+ 1 
            (calculateWordSizeReal
              cardinalNumber
              index
              (+ sum (potenz cardinalNumber exp))
              (+ 1 exp)))))))
  (calculateWordSizeReal (cardinalNumber set) index 0 1))))

(define createWord
  (lambda (set wordnumber cardinalNumber lettersRemaining)
    (if (= 0 lettersRemaining)
      ""
      (let ((sectionSize (potenz cardinalNumber (- lettersRemaining 1))))
        (let ((rest (modulo wordnumber sectionSize))
            (result (quotient wordnumber sectionSize)))
          (if (= 0 rest)
            (string-append
              (string (getElement set result))
              (createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
            (string-append
              (string (getElement set (+ result 1)))
              (createWord set rest cardinalNumber (- lettersRemaining 1)))))))))

(define numberOfWords
  (lambda (cardinalNumber letterCount)
    (if (= letterCount 0)
      0
      (+
        (potenz cardinalNumber letterCount)
        (numberOfWords cardinalNumber (- letterCount 1))))))

(define getElement
  (lambda (set index)
    (if (= index 1)
      (car set)
      (getElement (cdr set) (- index 1)))))

(define potenz
  (lambda (zahl exponent)
    (if (= exponent 0)
        1
        (* zahl (potenz zahl (- exponent 1))))))

(define wort-laenge-eins
  (lambda (wort)
    (- (length wort) 1)))

</code>

<code id="508d8bc6ef735">

(define S '(#\a #\b))

(define my-goedel
 (lambda (wort)
   (cond
     [(and (null? (cdr wort))(eqv? (car wort) #\a)) 1]
     [(and (null? (cdr wort))(eqv? (car wort)#\b)) 2]
     [(eqv? #\a (car wort)) (+ (my-goedel (cdr wort)) (* 1 (potenz 3 (wort-laenge-eins wort)))) ]
     [(eqv? #\b (car wort)) (+ (my-goedel (cdr wort)) (* 2 (potenz 3 (wort-laenge-eins wort)))) ]
     [else #f])))


(define h
  (lambda (wort)
    (my-goedel (string->list wort))))

</code>

Gödelisierung h (Verschlüsselung im 3-er System):

<run id="508d8bc6ef98b">
(h "aba")
</run>

<code id="508d8bc6ef79f">
(define g
  (lambda (i m z)
    (cond
      [(equal? 0 z) (display "...")  ]
      [(= (monus-minus (p i m)) 0)  (display m)(display ", ") (g (+ m 1) 0 (- z 1)) ]
      [else (g i (+ m 1) z)])))

(define monus-minus
  (lambda (y)
    (if (<= 1 y) 0 (- 1 y))))

(define g-n-mal
  (lambda (n)
    (g 0 0 n)))
</code>
 
Die ersten n Gödelnummern:

<run id="508d8bc6efa00">
(g-n-mal 15)
</run>

<code id="508d8bc6ef808">

(define is-goedel?
  (lambda (y index)
    (cond
      [(eqv? (my-goedel(string->list(f index))) y) #t]
      [(>(my-goedel(string->list(f index))) y) #f ]  
      [else (is-goedel? y (+ index 1))])))

(define goedel-nummer?
  (lambda (nr)
    (is-goedel? nr 1)))

</code>

Prozedur goedel-nummer? prüft, ob es sich um eine gültige Gödelnummer handelt:

<run id="508d8bc6efa69">
(goedel-nummer? (h "abba"))
</run>
<run id="508d8bc6efadb">
(goedel-nummer? 10)
</run>

<code id="508d8bc6ef873">
(define p
  (lambda (r y)
    (if (and (<= r y) (goedel-nummer? y)) 1 0)))
</code>

Scheme-Prozedur für ein total berechenbares Prädikat p:

<run id="508d8bc6efb4c">
(p 3 3)
</run>
<run id="508d8bc6efbbf">
(p 3 4)
</run>

<code id="508d8bc6ef8df">

(define f (fCreator S))
  
(define k
  (lambda (n)
    (f n)))


</code>

Prozedur k liefert das n-te Wort in der gödelgeordneten Folge der Wörter aus S*:

<run id="508d8bc6efc33">
(h (k 10))
</run>
<run id="508d8bc6efca8">
(k 10)
</run>

Aufgabe 1

<code id="508e4d9ac99d3">


(define gerade
  (lambda (x y)
    (if (equal? (+ (modulo x 2) y) 0 ) y
        (gerade x (+ y 1))))) 
    
(define gerade-x
  (lambda (x)
    (gerade x 0)))

</code>

Wenn x gerade, dann 0, sonst stoppt nicht.

<run id="508e4d62ec556">
(gerade-x 6)
</run>

<run id="508e4d62ec611">
(gerade-x 3)
</run>

Aufgabe 2

<code id="508e4c0c33d52">

(define h1
  (lambda (x y)
    (if (equal? (- (modulo x 2) y) 0) y
        (h1 x (+ y 1)))))

(define h1-x
  (lambda (x)
    (h1 x 0)))

</code>

Wenn x gerade, dann 0, sonst 1.

<run id="508e4c0c34489">
(h1-x 4)
</run>

<run id="508e4c0c3459e">
(h1-x 5)
</run>

Aufgabe 3

<code id="508e4c0c33e2b">

(define monus-minus
  (lambda (x y)
    (if (<= x y) 0 (- x y))))

(define h2
  (lambda (x y)
    (if (equal? (monus-minus (pow x 2) y) 0) y
        (h2 x (+ y 1)))))

(define h2-x
  (lambda (x)
    (h2 x 0)))

</code>

x-quadrat

<run id="508e4c0c346a5">
(h2-x 3)
</run>

Aufgabe 4

<code id="508e4c0c33f02">

(define h3
  (lambda (x y)
    (if (equal? (monus-minus (pow y 2) x) 0) y
        (h3 x (+ y 1)))))

(define h3-x
  (lambda (x)
    (h3 x 0)))

</code>

Liefert 0.

<run id="508e4c0c347ac">
(h3-x 5)
</run>

Aufgabe 5

<code id="508e4c0c33ff4">

(define prim?
  (lambda (n)
    (letrec
      ((helfer
	(lambda (t)
	  (cond
	    ((> t (sqrt n)) 1)
	    ((= (remainder n t) 0) 0)
	    (else
	      (helfer (+ t 2)))))))
      (cond
	((= n 1) 0)
	((= n 2) 1)
	((= (remainder n 2) 0) 0)
	(else
	  (helfer 3))))))

(define x-kleiner-y
  (lambda (x y)
    (if (< x y) 1 0)))
 

(define h4
  (lambda (x y k)
    (if (equal? (- (* (x-kleiner-y x y) (prim? y)) k) 0) k
    (h4 x y (+ k 1)))))


(define h4-x-y
  (lambda (x y)
    (h4 x y 0)))

</code>

Wenn y eine Primzahl größer als x, dann 1, sonst 0.

<run id="508e4c0c348d3">
(h4-x-y 3 5)
</run>

<run id="508e4c0c349f6">
(h4-x-y 6 5)
</run>


Aufgabe 6

<code id="508e4c0c340c9">

(define potenz
  (lambda (zahl exponent)
    (if (= exponent 0)
        1
        (* zahl (potenz zahl (- exponent 1))))))

(define betrag
  (lambda (x)
    (cond
      [(< x 0) (* -1 x)]
      [else x])))

(define signum
  (lambda (x)
    (cond
      [(> x 0) 1]
      [(= x 0) 0]
      [(< x 0) -1]
      [else #f])))

(define g
  (lambda (m n k)
   (cond
    [(equal? (potenz (- (* k m) n) (signum m)) 0) k]
    [else (g m n (+ k 1))])))

(define g-m-n
  (lambda (m n)
    (g m n 0)))

</code>

Wenn m ungleich 0 UND m teilt n.

<run id="508e4c0c34afa">
(g-m-n 4 8)
</run>

<run id="508e4c0c34be4">
(g-m-n 4 6)
</run>

<run id="508e4ebeb28f4">
(g-m-n 0 6)
</run>