Satz von Kleene < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:21 Mo 20.05.2013 | | Autor: | chesn |
| Aufgabe | Satz von Kleene: Für jede n-stellige μ-rekursive Funktion $ f $ gibt es zwei $(n+1)$-stellige primitiv rekursive Funktionen $ p $ und $ q $ , sodass sich $ f $ wie folgt darstellen lässt:
[mm] $f(x_1,...,x_n)=p(x_1,...,x_n,\mu q(x_1,...,x_n)).
[/mm]
Wahr oder falsch? Nach diesem Satz gilt, dass...
a) ...sich jede μ-rekursive Funktion ausschließlich durch eine festgelegte Komposition von primitiv rekursiven Funktionen darstellen lässt.
b) ...jede μ-rekursive Darstellung - neben primitiv rekursiven Funktionen - mindestens einen μ-Operator enthalten muss.
c) ...es für jede μ-rekursive Funktion eine μ-rekursive Darstellung mit höchstens einem Vorkommen des μ-Operators gibt. |
Hallo! Die Aufgabe ist aus der theoretischen Informatik, dennoch hoffe ich, dass mir hier evtl. jemand weiter helfen kann.
a) Wahr.
b) Falsch. Wenn ich das richtig verstanden habe, muss der μ-Operator nicht zwingend vorkommen.
c) Ich tendiere zu wahr, mich stört allerdings das "höchstens". Kann der μ-Operator mehrmals vorkommen?
Wäre nett wenn mir jemand sagen könnte, ob ich das so richtig sehe.
Vielen Dank schonmal!
chesn
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 22.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
