Vorlesung 2 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-03-29T07:18:55+00:00. Aktuelle Version

Absolute Unlösbarkeit

Seite 7

(define f
  (lambda (n)
    (if (= n 1)
        1
        (if (even? n)
            (+ (f (/ n 2)) 1)
            (/ 1 (f (- n 1)))
            )
        )
    )
  )

(f 1)

f(1) = 1 f(2) = 2 f(3) = 1 / f(2) = 0.5 f(4) = f(4/2) + 1 = f(2) + 1 = 3 f(5) = 1 / f(4) = 1/3 f(6) = f(3) + 1 = 1.5 f(7) = 1 / f(6) = 1 * 2/3 = 2/3

(define f^-
  (lambda (n)
    (if (= n 1)
        1
        (if (> n 1)
            (* (f^- (- n 1)) 2)
            (+ (f^- (/ 1 n)) 1)
            )
        )
    )
  )

(f^- 1)

Überabzählbar unendlich

Seite 11

z.z: \mathbf{R} ist überabzählbar unendlich

Beweis: Widerspruch mit Cantorsches Diagonalisierungsverfahren 2. Art

Annahme: \mathbf{R} ist abzahlbar unendlich

Listen aller rellen Zahlen r_n:


\|\| s1 \|\| s2 \|\| s3 \|\| s4 \|\| ...
r1 0.	\textbf{1}	4	1	5	...
r2 0.	7	\textbf{1}	8	2	...
r3 0.	6	1	\textbf{8}	0	...
r4 0.	4	1	4	\textbf{2}	...
...	...	...	...	...	...

Wahl der Ziffern auf der Diagonalen und Zusammenstellen einer neuen Zahl mit den entsprechenden Stellen s_n aus der Tabelle.

r_{comp} = 0.1182...

Dabei werden die Ziffern abgeändert wobei jede 1 zu einer 2 wird und jede andere Ziffer zu einer 1.

r_{new} = 0.2211...

Dadurch unterscheidet sich diese neue Zahl von jeder aufgelisteten, da sie sich von r1 an der ersten Stelle unterscheidet, von r2 an der 2. Stelle von r3 an der 3. Stelle usw..

Hilbert Hotel

(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

(define-macro (stream-cons head tail)
  `(cons ,head (delay ,tail)))

(define stream?
  (lambda (stm)
    (and (pair? stm) (promise? (cdr stm)))))

(define stream-map
  (lambda (proz stm)
    (stream-cons (proz (stream-car stm)) (stream-map proz (stream-cdr stm)))))

(define show-stream
  (lambda (stm n)
    (letrec
        ([show
          (lambda (stm n ls)
            (if (= n 0)
                (apply display (append ls (list "...")))
                (show (stream-cdr stm) (- n 1) (append ls (list (stream-car stm) ", ")))))])
      (show stm n ()))))

(define zeige-mir show-stream)

(define baue-hilberthotel
  (lambda ()
    (stream-cons #f (baue-hilberthotel)))
  )

(define hilberthotel (baue-hilberthotel))

(zeige-mir hilberthotel 11)

(define einzelbuchung
  (lambda (val stm pos)
    (let ([old-pos pos])
      (letrec
          ([shorten
            (lambda (val stm pos)
              (if (= pos 0)
                  (if (eq? #f (stream-car stm))
                      (stream-cons val (stream-cdr stm))
                      (raise (string-append (number->string old-pos) " schon belegt mit: " (stream-car stm))))
                  (stream-cons (stream-car stm) (shorten val (stream-cdr stm) (- pos 1)))
                  ))
            ])
        (shorten val stm pos)
        )
      )
    )
  )

(set! hilberthotel (einzelbuchung "Otto Grundmann" hilberthotel 3))
(zeig-mir hilberthotel 12)

(define baue-kleinbus
  (lambda (numb pers)
    (list numb pers)))


(define kleinbus815 (baue-kleinbus 815 8))

(zeig-mir kleinbus815)

(define kleingruppenbuchung
  (lambda (hotel finite-bus)
    (letrec
        ([helper
          (lambda (hotel finite-bus pos)
            (if (not (empty? finite-bus))
                (helper (einzelbuchung (car finite-bus) hotel pos) (+ pos 1))
                (hotel)
                )
            )
          ])
      (hotel finite-bus 0)
      )
    )
  )

(set! hilberthotel (kleingruppenbuchung kleinbus815 hilberthotel))

(zeig-mir hilberthotel 12)

Vorlesung 2 Grüning

Absolute Unlösbarkeit

Überabzählbar unendlich

Hilbert Hotel

Suche