\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Computer Architecture 1 - Übungsblatt 10}
\author{Dirk Heine, 2030941 \\
	Jan Hendrik Dithmar, 2031259 \\
	Steffen Heil, 2019358
}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
Zuerst muss bei der rekursiven Definition eine Substitution von $t+1$ durch $t$ durchgeführt werden:
$$byte(b,M^t_I[ad]) = \left\{ \begin{array}{lcl}byte(b,din^{t-1}) & : & M_I.bw(ad,b)(t-1) \\ byte(b,M^{t-1}_I[ad]) & : & else\end{array} \right.$$
Fallunterscheidung:
\begin{enumerate}
	\item Fall: $M_I.bw(ad,b)(t)=0$ \\
		Wendet man die rekursive Definition oft genug an, ist man irgendwann beim Zeitpunkt $t=0$. Das bedeutet, laut Definition von \glqq initial memory\grqq , dass
		$$byte(b,M^t_I[ad]) = byte(b,M^{t-1}_I[ad]) \Longleftrightarrow byte(b,M^t_I[ad]) = byte(b,initmem)$$
	
	\item Fall: $M_I.bw(ad,b)(t)=1$ \\
		Annahme: $\forall t''$ mit $t' < t'' < t$ gilt: $M_I.bw(ad,b)(t'')=0$ \\
		Das bedeutet: ich wähle solange den else-Teil, bis ich bei $last_P(t'') + 1$ angekommen bin. Danach bin ich bei $last_{M_I.bw(ad,b)}(t'') = t$ angekommen. Somit kann man $din^t$ durch $din^{last_{M_I.bw(ad,b)}(t)}$ ersetzen.
\end{enumerate}
Somit kann man in beiden Fällen die rekursive auf die nicht-rekursive Definition zurückführen.


\newpage

\section*{Aufgabe 2}
\bild{6}{a2_1.jpg}{Aufgabe 2, Abbildung 1}{a21}
\bild{6}{a2_2.jpg}{Aufgabe 2, Abbildung 2}{a22}

\end{document}