Test GR2

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f(0)=1$ $f(1)=3$ $f(n)=n+3;n\ge 2$	$f(0)=2$ $f(1)=3$ $f(n)=n+1;n\ge 2$
Maszyna rozpoznająca $w{w}^{\leftarrow }$	$f(n)=6+8+\dots +(n+3)+2;n=2k+1$ $f(n)=5+7+\dots +(n+3)+1;n=2k$	$f(n)=n+1$

$\Rightarrow$	0	1	...	...
Cell1	Cell2

$\Rightarrow$	0	1
0	1	1
1	0	1

$p$	$\mathrm{\neg }p$
0	1
1	0

$\wedge$	0	1
0	0	0
1	0	1

$\vee$	0	1
0	0	1
1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p} \wedge \textnormal{q}}	$\mathrm{\neg }(p\wedge q)$	$\mathrm{\neg }p$	$\mathrm{\neg }q$	$\mathrm{\neg }p\vee \mathrm{\neg }q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p\wedge r)$	$(q\wedge \mathrm{\neg }r)$	$(p\wedge r)\vee (q\wedge \mathrm{\neg }r)$	$(p\wedge q)\Rightarrow ((p\wedge r)\vee (q\wedge \mathrm{\neg }r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Numer funkcji	$p=0$ $q=0$	$p=0$ $q=1$	$p=1$ $q=0$	$p=1$ $q=1$
0	0	0	0	0		$F$
1	0	0	0	1		$\wedge$
2	0	0	1	0		$\mathrm{\neg }(p\Rightarrow q)$
3	0	0	1	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}
4	0	1	0	0		$\mathrm{\neg }(q\Rightarrow p)$
5	0	1	0	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}
6	0	1	1	0		$XOR$
7	0	1	1	1		$\vee$
8	1	0	0	0		$NOR$
9	1	0	0	1		$\iff$
10	1	0	1	0		$\mathrm{\neg }q$
11	1	0	1	1		$q\Rightarrow p$
12	1	1	0	0		$\mathrm{\neg }p$
13	1	1	0	1		$p\Rightarrow q$
14	1	1	1	0		$NAND$
15	1	1	1	1		$T$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$(p\leftrightarrow q)$	$(p\leftrightarrow q)\leftrightarrow r$	$(q\leftrightarrow r)$	$p\leftrightarrow (q\leftrightarrow r)$
0	0	0	1	0	1	0
0	0	1	1	1	0	1
0	1	0	0	1	0	1
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$\circ (p,q,r)$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$f_{p{\to }_{(}q\to r)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

$\hat{\sigma }(f(t_0,..,t_n))=I(f)(\hat{\sigma }(t_0),..,\hat{\sigma }(t_n))$

$X^{*}=\{1\}\cup X\cup X^2\cup ...\cup X^n\cup \dots =\bigcup _{i=0}^{\mathrm{\infty }}{X}^i$

John Arthur Todd (1908-1994)
Zobacz biografię

Donald Ervin Knuth (1938-)
Zobacz biografię

Nagroda Turinga
Zobacz Nagroda Turinga