\documentclass[ article, 14pt ]{memoir}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage{epstopdf}
 
\usepackage{color}
\definecolor{Blue}{rgb}{0.3,0.3,0.9}
\definecolor{Red}{rgb}{0.9,0.3,0.3}
\definecolor{Green}{rgb}{0.3,0.9,0.3}
\definecolor{ared}{rgb}{.647,.129,.149}

\usepackage{xcolor}

\newtheorem{problem}{Problem}

\title{Oblig 2 --- INF 2080
\\ Innlevering mandag 18.mars}
\author{}




\begin{document}
\maketitle

Se p\aa{} reglement for oblig'er --- det ligger p\aa{} hjemmesidene til IFI. Om du er usikker p\aa{} hvordan en oppgave skal forst\aa{}s eller finner feil, redegj\o{}r for dette og deretter gj\o{}r dine egne presiseringer.


\chapter{Turing maskiner og fliselegging}

Vi har bare en oppgave. Der skal vi se p\aa{} det \aa{} simulere kj\o{}ring av en turing maskin med det \aa{} legge fliser.

\section{Konfigurasjonstabell}

La oss tenke oss at vi har en kj\o{}ring p\aa{} en turing maskin $\mathcal T$. Vi kan anskueliggj\o{}re kj\o{}ringen ved \aa{} legge tapen for tidspunkt 0, tidspunkt 1, tidspunkt 2 og s\aa{} videre under hverandre og vi f\aa{}r en tabell

\begin{tikzpicture}

\foreach \i in {0 , 1 , 2, 3, 4, 5, 6, 7, 8}
{\foreach \j in {0 , 1 , 2, 3, 4, 5, 6, 7, 8}
{\draw (\i,\j) rectangle +(1,1);}}

\draw[fill=red] (5,8) rectangle +(1,1) ;
\draw[fill=red] (6,7) rectangle +(1,1) ;
\draw[fill=red] (7,6) rectangle +(1,1) ;
\draw[fill=red] (6,5) rectangle +(1,1) ;
\draw[fill=red] (5,4) rectangle +(1,1) ;
\draw[fill=red] (4,3) rectangle +(1,1) ;
\draw[fill=red] (3,2) rectangle +(1,1) ;
\draw[fill=red] (4,1) rectangle +(1,1) ;
\draw[fill=red] (3,0) rectangle +(1,1) ;


\end{tikzpicture}

Her har jeg markert den aktive ruten --- ruten som blir lest og skrevet p\aa{} --- med r\o{}dt.



\begin{problem}
Hva i tabellen svarer til tapen p\aa{} turing maskinen i et gitt tidspunkt ?
\end{problem}

En rad i tabellen kaller vi ofte en konfigurasjon og hele tabellen for en konfigurasjonstabell.



Beregningen p\aa{} turing maskinen bruker ressurser --- den bruker tid og rom.


\begin{problem}
Hva svarer til tid og rom i v\aa{}r tabell ?
\end{problem}



P\aa{} beregninger med turing maskiner er det forbindelse mellom bruk av tid og bruk av rom. 

\begin{problem}

Gi argument for
\begin{itemize}
\item Rom vokser line\ae{}rt i tiden.
\item Med begrenset rom vil samme rad gjenta seg innen eksponensiell bruk av tid.
\end{itemize}
\end{problem}



\section{En konkret turing maskin}

N\aa{} ser vi p\aa{} kj\o{}ringer av en konkret turing maskin. Vi har valgt f\o{}lgende, $\mathcal B$, med start p\aa{} blank tape

$$
\begin{tikzpicture}[scale=2.0]

\path  (0,0) node (0) {} ;
\path  (1,0) node[draw, shape=circle,  shading=ball] (1) {};
\path  (3,0) node[draw, shape=circle,  shading=ball] (2) {};
\path  (5,0) node[draw, shape=circle,  shading=ball] (3) {};
\path  (7,0) node (H) {\tiny H} ;

\draw[->] (0) -- (1) ;
\draw[->] (1) .. controls +(1,0.2) and +(-1,0.2) .. node[above] {\tiny 0 $\rightarrow$ 1,R} (2); 
\draw[->] (2) .. controls +(-1,-0.2) and +(1,-0.2) .. node[below] {\tiny 0 $\rightarrow$ 1,L} (1) ;
\draw[->] (1) .. controls +(1,-1) and +(-1,-1) .. node[below] {\tiny 1 $\rightarrow$ 1,L} (3) ;
\draw[->] (2) .. controls +(-1,1) and +(1,1) .. node[above] {\tiny 1 $\rightarrow$ 1,R} (2) ;
\draw[->] (3) -- node[above] {\tiny 0 $\rightarrow$ 1,L} (2);
\draw[->] (3) -- node[above] {\tiny 1 $\rightarrow$ 1,R} (H) ;

\end{tikzpicture}
$$

Maskinen er en flittig bever med 3 tilstander og stopp-tilstand.


\begin{problem}
Lag en transisjonstabell for $\mathcal B$. Hvor mange linjer har den?
\end{problem}

Med en transisjonstabell for en turing maskin mener vi tabellen med 5 kolonner --- symbol lest, tilstand, symbol skrevet, ny tilstand, bevegelse.

\section{Oversettelse til fliselegging --- hvilke typer fliser}

V\aa{}re fliser ser slik ut:

$$\begin{tikzpicture}[scale=1.0]

\draw[fill=red] (0,0) -- (2,0) -- (1,1) -- cycle;
\draw[fill=green] (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=yellow] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw[fill=blue] (0,0) -- (0,2) -- (1,1) -- cycle;



\end{tikzpicture}$$

De har alle bestemte sider som er OPP - H\O{}YRE - NED - VENSTRE. De er alts\aa{} orientert. Problemet med fliselegging er \aa{} legge flisene slik at sidene som ligger inntil hverandre har like farger.

Gitt en turing maskin $\mathcal T$ vi kan lage fliser som svarer til maskinen. Vi har f\o{}lgende oversettelse:

\begin{description}
	\item[Hver a i alfabetet:] 

	\begin{tikzpicture}[scale=1.0]

\draw[fill=red!30] (0,0) -- (2,0) -- (1,1) -- cycle ;
\draw (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=red!30] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw (0,0) -- (0,2) -- (1,1) -- cycle;

\draw (1,0.5) node {\tiny a};
\draw (1,1.5) node {\tiny a} ;

	\end{tikzpicture}
	\item[Transisjon (b,p $\rightarrow$ c,q,R):]
	
	\begin{tikzpicture}[scale=1.0]

\draw[fill=red!30] (0,0) -- (2,0) -- (1,1) -- cycle;
\draw[fill=green!30] (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=yellow!30] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw  (0,0) -- (0,2) -- (1,1) -- cycle;


\draw (1,1.5) node {\tiny (b,p)};
\draw (1,0.5) node {\tiny c} ;
\draw (1.5,1) node {\tiny q} ;

	\end{tikzpicture}
	\item[Transisjon (b,p $\rightarrow$ c,q,L):]
	
	\begin{tikzpicture}[scale=1.0]

\draw[fill=red!30] (0,0) -- (2,0) -- (1,1) -- cycle;
\draw (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=yellow!30] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw[fill=blue!30] (0,0) -- (0,2) -- (1,1) -- cycle;

\draw (1,1.5) node {\tiny (b,p)};
\draw (1,0.5) node {\tiny c} ;
\draw (0.5,1) node {\tiny q} ;

	\end{tikzpicture}
\item[Hver b i alfabetet og q tilstand:]
	
	\begin{tikzpicture}[scale=1.0]

\draw[fill=red!30] (0,0) -- (2,0) -- (1,1) -- cycle;
\draw (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=yellow!30] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw[fill=green!30] (0,0) -- (0,2) -- (1,1) -- cycle;

\draw (1,1.5) node {\tiny b};
\draw (1,0.5) node {\tiny (b,q)} ;
\draw (0.5,1) node {\tiny q} ;

	\end{tikzpicture}
og
\begin{tikzpicture}[scale=1.0]

\draw[fill=red!30] (0,0) -- (2,0) -- (1,1) -- cycle;
\draw[fill=blue!30] (2,0) -- (2,2) -- (1,1) -- cycle;
\draw[fill=yellow!30] (2,2) -- (0,2) -- (1,1) -- cycle;
\draw (0,0) -- (0,2) -- (1,1) -- cycle;

\draw (1,1.5) node {\tiny b};
\draw (1,0.5) node {\tiny (b,q)} ;
\draw (1.5,1) node {\tiny q} ;


\end{tikzpicture}
	
For hver type har vi ubegrenset mange fliser av den typen. Fargene er markert med symboler og par av symboler.	
	
	
\end{description}

\begin{problem}
Hvilke typer fliser svarer til turing maskinen $\mathcal B$ ? Hvor mange farger bruker vi ?
\end{problem}

\section{Oversettelse til fliselegging --- kj\o{}ring}

Vi ser stadig p\aa{} turing maskinen $\mathcal B$ og oversettelsen til et fliseleggingsproblem


\begin{problem}
\begin{itemize}
\item Hva svarer til start av kj\o{}ringen ?
\item Hva svarer til stopp av kj\o{}ringen ?
\item Vis at fra en rad er det bare en mulig neste rad
\item Vis at det finnes n\o{}yaktig en m\aa{}te \aa{} fliselegge ved \aa{} bruke flisene til $\mathcal B$
\end{itemize}
\end{problem}



\section{Generaliseringer}

\begin{problem}
V\aa{}re turing maskiner var deterministiske. Hva ville skje med ikke-deterministiske turing maskiner ?  Hva tror du ?
\end{problem}


\begin{problem}
Skisser hvordan du vil lage et flisesystem for -- la oss si -- multiplikasjon.
\end{problem}


\begin{problem}
Fargene i v\aa{}re fliser brukes bare for \aa{} uttrykke at flisene skal passe sammen --- side mot side. I stedet for farger kunne vi ha brukt inn- og utbuktninger p\aa{} sidene akkurat som i et puslespill. Skisser hvordan du kunne gj\o{}re dette.
\end{problem}

\begin{problem}
Hva svarer til at stoppeproblemet er uavgj\o{}rbart for turing maskiner --- i v\aa{}r fliseleggingsverden.
\end{problem}

\begin{problem} 
I kompleksitetsteori skal vi snakke om polynomiell tid og rom for deterministiske og ikke-deterministiske turing maskiner. Hva svarer det til i v\aa{}r fliseleggingsverden.
\end{problem}

\end{document}