Kombinatorische Logik
(λx.x)a=>a
Ia=>a
λx.x=>I
λxy.x=>K K ab=>a
λxyz.xz(yz)=>S
(λxyz.xz(yz))abc=>ac(bc)
Sabc=>ac(bc)
16.01.2013
I - Identitätskombinator Ix=>x
K- Kanzelator Kxy=>x
S- Verschmelzungskombinator S abc => ac(bc)
(SKK)x => Kx(Kx) => x => Ix
Regel0: T [λx.(exp)]=>[elim. x] exp
Regel1: [elim x] x => I
T [λx.x] => [elim x] x => x
Regel2: [elim x] y => K y
T[(λx.y)] => [elim x] y
Regel3: [elim x] exp1 exp2 => S ([elim x]exp1) ([elim x])exp2)
[elim x] xy => S I (Ky)
T[(λx.(λy.x(y)))] | 1 in Lambda
=> [elim x](λy.x(y)) |Regel0
=> [elim x]([elim y](x(y)) |Regel0
=> [elim x](S ([elim y] x)([elim y] y)) |Regel3
=> [elim x] (S(Kx)I) |Regel1 Regel2
=> S([elim x](S(K x)))([elim x] I) |Regel3
=> S (S([elim x]S)([elim x](Kx)))(KI) |Regel3 Regel2
=> S (S(KS)(S([elim x] K)([elim x] x)))(KI) |Regel3
=> S (S(KS)(S(KK)I))(KI) | 1 in Kombinatorenausdruck
(λx.λy.x(y)) f a => f a
(S(S(KS)(S(KK)I))(KI)) f a
=> (S(KS)(S(KK)I))f((KI)f)a
=> (KS)f((S(KK)I)f)((KI)f)a
=> S ((S(KK)I) f)((KI)f)a
=> S ((KK)f(If)((KI)f)a
=> S (K f) I a
=> (Kf)a (I a)
=> f Ia
=> f a
Band:
..|A|(|(|)|(|(|)|)|)|A|..
der Kopf steht am Anfang auf A
er rückt nun nach Rechts bis er ")" findet
für ")" wird "x" geschrieben, und der Kopf rückt solange nach Links bis er "(" findet und ersetzt auch diese durch "x"
findet er keine Rückt er bis zum A und ersetzt dieses durch "0"
ließt er das A am Ende, dann schreibt er ein A und geht zurück zum A und schreibt eine 1, vorrausgesetzt, er ließt keine "(", dann schreibt er eine "0"
21.01.13
Zs: A->A,R,Z1
Z1:(->(,R,Z1
)->x,L,Z2
x->x,R,Z1
A->A,L,Z3
Z2:(->(,R,Z1
x->x,R,Z2
A->0,S,Z2
Z3:x->x,L,Z3
A->1,S,Ze
(->(,L,Z4
Ze:Endzustand
Z4:A->0,S,Z4
0->0,S,Z4
(->(,L,Z4
TM=(Q,A,B,F,Start,(Band-)leerzeichen,halt)
Q={Zs,Z1,Z2,Z3,Z4,Z3}
A={A,x,(,)}
B={A,x,(,),0,1,_}
F= [siehe oben]
Start=Zs
halt=Ze
(Band-)Leerzeichen=_
...|_|B|B|B|B|B|B|_|
...|_|1|x|B|B|B|B|B|_|
...|_|1|0|x|x|B|B|B|B|_|
Zs: 'B'->'x',L,Z1
'_'->'_',R,Z2
0->0,R,Zs
1->1,R,Zs
'x'->'x',R,Zs
Z1:'_'->1,R,Zs
'1'->'0',L,Z1
'0'->'1',R,Zs
'x'->'x',L,Z1
Z2:x->_,L,Z2
1->1,S,Z3
0->0,S,Z3
23.01.2013
unary2binary
...B|B|B|B|B|B|B|...
q1:_,_,L,q3
0,0,R,q1
1,1,R,q1
X,X,R,q1
B,X,L,q2
q2:1,0,L,q2
_,1,L,q1
0,1,R,q1
q3:X,_,L,q3
0,0,S,qe
1,1,S,qe
Komplexität:O(n^2)
Version 2
...|B|B|B|B|B|B|B|B|...
q1:B,X,R,q2
_,_,L,q3
q2:B,B,R,q1
_,_,L,q5
q3:_,0,R,q4
q4:B,X,R,q2
_,_,S,qe
q5:_,1,R,q4
Komplexität:O(n* log_2 (n))
collatz-Funktion
collatz n| n==1 = 1
| gerade n=collatz (div n 2)
| ungerade n= collatz (n*3+1)
...|1|0|1|1|1|1|0|...
...|1|0|1|1|1|1|0|...
...|1|0|1|1|1|1|0|...
+|1|0|1|1|1|1|0|...
...|1|0|0|0|1|1|0|1|...
q1:0,_,L,q1
1,1,L,q2
q2:_,_,R,qe
0,0,S,q3
1,1,S,q3
q3:1,0,L,q4
0,1,L,q5
_,1,R,q6
q4:1,1,L,q4
0,0,L,q3
_,0,L,q3
q5:0,0,L,q5
1,1,L,q3
q6:0,0,R,q6
1,1,R,q6
_,_,L,q7
q7:1,0,L,q7
0,1,L,?????
_BBBBBB_
B->
X->
_->
0->
1->
A->11
X->01
(->10
)->00
28.01.2013
g(a,b,c)=f(a,a,c,b) wenn f(x1,x2,x3,x4) primitivrekursiv
g(a,b,c)=f(π_(1)^(3)(a,b,c),π_(1)^(3)(a,b,c),π_(3)^(3)(a,b,c),π_(2)^(3)(a,b,c))
isZero(0)=C_(1)^(0)()=S(Z)=1
isZero(S(n))=C_(0)^(2)(isZero(n),n)=0
nott= isZero
false =0 true =1
0 0 0
0 1 0
1 0 0
1 1 1
andd= mult
leq(n,m)=isZero(sub(π_(1)^(2)(n,m),π_(2)^(2)(n,m))
leq=isZero ° sub
ungerade 0= C_(0)^(0)
ungerade (S(n))=nott(π_(1)^(2)(ungerade(n),n))
ungerade(4)=>nott(ungerade(3))
=>nott(nott(ungerade(2)))
=>nott(nott(nott(ungerade(1))))
=>nott(nott(nott(nott(ungerade 0))))
=>0
min(x,y)=(x-(x+y))
min(x,y)=sub°[π_(1)^(2)(x,y),sub[π_(1)^(2)(x,y),π_(2)^(2)()]]
30.01.2013
min(x,y)=(x-(x-y))
x<y:
x-(x-y)=>x
x-y=>0
x>y:
x-(x-y)=>y
x-y=>k
minn:ℕ^2->ℕ
minn(x,y)=sub(π[2,1](x,y),sub(π[2,1](x,y),π[2,2](x,y)))
(rec(n),n)
(add(n,m),n,m)
add(0,m)=m
mult(0,m)=0
mult(S(n),m)=add(π[3,1](mult(n,m),n,m),π[3,3,(mult(n,m),n,m))
g=C[1,0]
h=add○[π[3,1],π[3,3]]
minn=compose sub [(p 1), compose sub [(p 1), (p 2)]]
minn[x,y]=sub [x, sub [x,y]]
Fakultät
g:ℕ^0->ℕ g=C[0,1]
h:ℕ^2->ℕ h= mult○[S○π[2,2],π[2,1]]
f(0)=C[0,1]
f(S(n))=mult(S(π[2,2](f(n),n)),π[2,1](f(n),n))
const 2 _=2
rec g h
factorial=pr factorial (const 1) (compose mult [compose s [(p 2)], (p 1)])
half (0)=0
half (S(n))=half(n)+ungerade(n) |abgerundet
0 1 2 3 4
half(5)=(half(0)+1+0+1+0) =2
half (0)=C[0,0]
half(S(n))=add(π[2,1](half(n),n),ungerade(π[2,2](half(n),n)))
half
g=C[0,0]
h=add○[π[2,1],ungerade○[π[2,2]]]
half[n]=pr half (const 0) (compose add[(p 1), (compose ungerade[(p 2)]]
Division (Ganzzahlig)
idiv x y | x>=y = 1+ idiv (x-y) (y)
| otherwise =∅
sub ∅ (k-1)
x/y=1*y - x + 2*y-x+...+k*y-x
nott ∅ nott∅ 1
1 1 ∅
idiv(x,y)=pred(idiv'(S(x),y,x))
idiv=compose predd (compose idiv'[ compose s [(p 1)],(p 2),(p 1)]])
idiv'[n,y,x]=pr idiv' g h [n,y,x] |n=y+1
where
g= const ∅
h=compose add [(P 1), compose nott [compose sub [compose mult [(P 2),(P 3)], (P 4)]]
x y
3/1=((2*3)-3)+((1*3)-3)+((0*3)-3)
1
1=true
0=false
iff [x,y,z] =pr iff (P 2) (P3) [x,y,z]
cond :: PRFunction
cond =compose add [compose mult [(compose sub[const 1, (compose isZero[(P 1)])](P 2)], (compose mult[(compose isZero(P 1)]),(P 3)])]
cond [test,f1,f2]
04.02.2013
f:ℕ^2->ℕ
f(m, z)={1 falls Student mit Matrikelnummer m im Semester z keinen Bachelor; 0 sonst
m-Matrikelnummer; z-Semester
06.02.2013
Konzepte:
Referenzielle Transperenz
Currify
binSearch b [ ] = False
binSearch b [x] =b==x
binSearch b xs | b< mitte =binSearch b links
| b > mitte =binSearch b rechts
| b==mitte =True
where
n half = (length xs) 'div' 2
n/2 links = take half xs
n/2 rechts = drop half xs
1 mitte =head rechts
=2n+1
binSearch b [x1, x2, ......, xn]
2n
[........]
2n/2
[...]
2n/4
2(n+n/2+n/4+n/8+n/16....)=2(n+n)=4n => O(n)
subSet [ ] _ = True
subSet _ [ ] =False
subSet (x:xs) ms = (inSet x ms) 18 (subSet xs) ms |inSet=elem
[x1,x2,...,xn] [y1,...,ym]
O(n^2)
T[λx.λy.(yx)]
=>T[λx.T[λy.(yx)]]
=>T[λx.(ST[λy.y]T[y.x])]
=>T[λx.(SI(Kx))]
=>(ST[λx.(SI)]T[λx.(Kx)]
=>S(K(SI))(ST[λx.K]T[λx.x])
=>S(K(SI))(S(KK)I)
Sonderzeichen: λ, Λ, π, ℕ, ○, ∅