blob: 4ed43f722fcec5e34189e0631944889257995a4d (
plain) (
blame)
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
|
% 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 de Esolang wiki gevonden dat een
string zou omdraaien~\cite{esolang:prog}. Dit programma werkte echter niet naar
behoren: het werkte niet voor strings met lengte $1$. Daarom hebben we zelf een
programma geschreven voor het omdraaien van een string. Dit programma ziet er
als volgt uit:
\begin{smurf}
\label{pgm:reverse}
\footnotesize
i "input" p
"input" g
"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
g x
\end{smurf}
Het bovenstaande programma is correcte Smurfsyntax en hierdoor niet erg
leesbaar. We hebben daarom getracht het programma iets leesbaarder te maken:
\input{reverse2}
\input{explanation}
\input{analyse-proof}
|
