1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
% vim: set spelllang=nl:
\section{Analyse}
\label{sec:analyse}
Omdat de transities van onze natuurlijke semantiek input meenemen, kunnen we
alleen een afleidingsboom maken voor een programma \emph{met} een bepaalde
input. Het is dus niet triviaal mogelijk een afleidingsboom te maken voor willekeurige
input. In deze sectie willen we laten zien hoe het toch mogelijk is een bewijs
te leveren over een programma met een willekeurige input string, door gebruik te maken
van inductie naar de lengte van de input string. We hadden hiervoor initieel een programma op het internet \cite{esolang:prog} gevonden welke een string zou moeten omdraaien. Echter werkte dit programma niet naar behoren. Het werkte namelijk niet voor strings met lengte een. Daarom hebben we zelf een programma geschreven voor het omdraaien van een string. Dit programma ziet er als volgt uit:
\begin{smurf}
\footnotesize
i "input" p
"input" g q
"\textbackslash{}"\textbackslash{}"\textbackslash{}"\textbackslash{}\textbackslash{}\textbackslash{}"u\textbackslash{}\textbackslash{}\textbackslash{}"p\textbackslash{}\textbackslash{}\textbackslash{}"v\textbackslash{}\textbackslash{}\textbackslash{}"p\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"p\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"gh\textbackslash{}\textbackslash{}\textbackslash{}"v\textbackslash{}\textbackslash{}\textbackslash{}"g+\textbackslash{}\textbackslash{}\textbackslash{}"v\textbackslash{}\textbackslash{}\textbackslash{}"p\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"gt
\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"p\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"g\textbackslash{}\textbackslash{}\textbackslash{}"v\textbackslash{}\textbackslash{}\textbackslash{}"gq\textbackslash{}\textbackslash{}\textbackslash{}"o\textbackslash{}\textbackslash{}\textbackslash{}"+\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"gq\textbackslash{}\textbackslash{}\textbackslash{}"v\textbackslash{}\textbackslash{}\textbackslash{}"gq\textbackslash{}\textbackslash{}\textbackslash{}"u\textbackslash{}\textbackslash{}\textbackslash{}"gq++\textbackslash{}\textbackslash{}\textbackslash{}"u\textbackslash{}\textbackslash{}\textbackslash{}"g+
\textbackslash{}\textbackslash{}\textbackslash{}"w\textbackslash{}\textbackslash{}\textbackslash{}"gp\textbackslash{}\textbackslash{}\textbackslash{}"\textbackslash{}\textbackslash{}\textbackslash{}"pgx\textbackslash{}"\textbackslash{}"u\textbackslash{}"p\textbackslash{}"v\textbackslash{}"p\textbackslash{}"w\textbackslash{}"p\textbackslash{}"w\textbackslash{}"gh\textbackslash{}"v\textbackslash{}"g+\textbackslash{}"v\textbackslash{}"p\textbackslash{}"w\textbackslash{}"gt\textbackslash{}"w\textbackslash{}"p\textbackslash{}"w\textbackslash{}"g\textbackslash{}"v\textbackslash{}"gq\textbackslash{}"o\textbackslash{}"+
\textbackslash{}"w\textbackslash{}"gq\textbackslash{}"v\textbackslash{}"gq\textbackslash{}"u\textbackslash{}"gq++\textbackslash{}"u\textbackslash{}"g+\textbackslash{}"w\textbackslash{}"gp\textbackslash{}"\textbackslash{}"pgx"
\\
+
"input" g p
"\textbackslash{}"\textbackslash{}"o" "" p
"input" g g x
\end{smurf}
Het bovenstaande programma is in het format van smurf maar echter is dit programma niet zo leesbaar.
Daarom hebben we getracht het programma iets leesbaardere te maken:
\input{reverse2}
\input{explanation}
\subsection{bewijs}
Nu laten we zien dat deze code daadwerkelijk alle mogelijke strings omdraait,
oftewel: er is een afleidingsboom voor
$$
\trans
{Programma}{[s:\Nil]}{(\Nil,\emptystore)}
{\Nil}{[s^R:\Nil]}{\st}
$$
voor alle s, waar
$$(c~s)^R=s^R c$$
$$\lambda^R=\lambda$$
\begin{proof}[Bewijs]
Met inductie naar de lengte van $s$.
Basisgeval: $s=\lambda$.
$$%Todo fix dit
\begin{prooftree}
\[
\[
\[
\[
\vdots %todo afmaken
\justifies
\trans
{\StmPut : \StmPush~\lambda : ...~}{\Nil}{([\lambda:["+":\Nil]], \emptystore)}
{\Nil}{\lambda}{\st}
\using{\rputns}
\]
\justifies
\trans
{\StmPush~\lambda : \StmPut : ...~}{\Nil}{(["+":\Nil], \emptystore)}
{\Nil}{\lambda}{\st}
\using{\rpushns}
\]
\justifies
\trans
{\StmCat : \StmPush~\lambda : ...~}{\Nil}{([\lambda:["+":\Nil]], \emptystore)}
{\Nil}{\lambda}{\st}
\using{\rcatns}
\]
\justifies
\trans
{\StmInput : \StmCat : ...~}{[\lambda:\Nil]}{(["+":\Nil], \emptystore)}
{\Nil}{\lambda}{\st}
\using{\rinputns}
\]
\justifies
\trans
{\StmPush~"+" : \StmInput : ...~}{[\lambda:\Nil]}{(\Nil,\emptystore)}
{\Nil}{\lambda}{\st}
\using{\rpushns}
\end{prooftree}
$$
%FIXME
NB: dit bewijs is overduidelijk niet af. We gaan de afleidingsboom
automatisch genereren, dit is nog maar een begin. Het programma, dat van de
Esolang wiki afkomstig is~\cite{esolang:prog}, werkt helaas niet voor strings
met minder dan twee karakters. In het geval van de lege string wordt geen
output gegeven; in het geval van een string van één karakter crasht het
programma. We zullen ofwel dit programma aanpassen, zodat het wel werkt,
ofwel een ander programma bekijken. In het laatste geval zullen we nog steeds
een programma nemen waar we iets inductief over kunnen bewijzen, zoals het
laatste voorbeeld uit \autoref{sec:intro:exmp}.
%todo afmaken
\end{proof}
|
