Datei:MonusTuringMachine.pdf

Größe der JPG-Vorschau dieser PDF-Datei: 800 × 342 Pixel. Weitere Auflösungen: 320 × 137 Pixel | 1.033 × 441 Pixel

Originaldatei (1.033 × 441 Pixel, Dateigröße: 37 KB, MIME-Typ: application/pdf)

Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.

Zur Beschreibungsseite auf Commons

Beschreibung

BeschreibungMonusTuringMachine.pdf	English: Turing machine to compute the truncated subtraction ("monus"), after John E. Hopcroft and Jeffrey D. Ullman (1979) Introduction to Automata Theory, Languages, and Computation, Reading/MA: Addison-Wesley ISBN: 0-201-02988-X. Example 7.2, page 151-153. To enhance understandibility, Hopcroft's and Ullman's input symbols "0", "1", and "B" (blank symbol) have been renamed to "I", "#", and "_", repectively; likewise, their states "q₀", ..., "q₆" have been renamed to "a", ..., "g". The machine is depicted in its start state, "a", and with its head in its start position on a tape representing the pair ⟨5,3⟩ in the unary numeral system. According to the book, in a computation of "m∸n", the intuitive meaning of the states is: a: Begin, replace the leading "I" by "_". b: Search right, looking for the first "#". c: Search right past "#"s until encountering an "I", change that "I" to "#". d: Move left to a "_", then enter state "a" again to repeat the cycle. e: In state "c", a "_" was encountered before an "I", each "I" of n was changed to "#", and n+1 "I"s of m were changed to "_". Now change all "#"s to "_"s until encountering a "_", change this "_" back to "I", and enter the stop state "g". f: In state "a", a "#" was encountered instead of an "I", that is m≤n, and each "I" of m was already changed to "_". Now erase the rest of the tape, and enter the stop state "g". g: Stop state. The computation is finished, the tape contains m∸n in unary notation, no further state changes are possible. See File:MonusTuringMachine ExampleRuns.gif for some example runs and a C simulator of this machine.
Datum	20. März 2019
Quelle	Eigenes Werk
Urheber	Jochen Burghardt
Andere Versionen	File:MonusTuringMachine.pdf — File:MonusTuringMachine_svg.svg — File:MonusTuringMachine ExampleRuns.gif

LaTeX source code

\documentclass[12pt]{article}
\setlength{\unitlength}{1mm}
\usepackage[pdftex]{color}
\usepackage{amssymb}
\usepackage[paperwidth=175\unitlength,paperheight=75\unitlength]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{175\unitlength}
\setlength{\textheight}{75\unitlength}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
\pagestyle{empty}

% colors
\definecolor{fState}    {rgb}{0.50,0.00,0.00}
\definecolor{fSym}      {rgb}{0.00,0.00,0.50}
\definecolor{fDir}      {rgb}{0.00,0.50,0.00}
\definecolor{bCtrl}     {rgb}{0.99,0.90,0.90}
\definecolor{bTape}     {rgb}{0.90,0.90,0.99}
\definecolor{bHead}     {rgb}{0.90,0.99,0.90}

\newcommand{\0}{\textcolor{fState}{a}}
\newcommand{\1}{\textcolor{fState}{b}}
\newcommand{\2}{\textcolor{fState}{c}}
\newcommand{\3}{\textcolor{fState}{d}}
\newcommand{\4}{\textcolor{fState}{e}}
\newcommand{\5}{\textcolor{fState}{f}}
\newcommand{\6}{\textcolor{fState}{g}}
\newcommand{\I}{\textcolor{fSym}{\tt\#}}
\renewcommand{\O}{\textcolor{fSym}{\tt I}}
\newcommand{\B}{\textcolor{fSym}{\tt\_}}
\renewcommand{\L}{\textcolor{fDir}{L}}
\newcommand{\R}{\textcolor{fDir}{R}}

\begin{document}
\begin{picture}(170,70)
% ctrl
\textcolor{bCtrl}{\put(45,35){\makebox(0,0)[bl]{\rule{92mm}{35mm}}}}%
\textcolor{white}{\put(60,57){\makebox(0,0)[bl]{\rule{5mm}{4mm}}}}%
\textcolor{fState}{\put(45.000,35.000){\framebox(92.000,35.000)[bl]{}}}%
\put(50.000,40.000){\makebox(0,0)[bl]{%
        \begin{tabular}{|c|*{7}{|c@{}c@{}c}|}%
        \multicolumn{22}{c}{\bf Finite control} \\
        \hline
                &\multicolumn{3}{c|}{\0}
                &\multicolumn{3}{c|}{\1}
                &\multicolumn{3}{c|}{\2}
                &\multicolumn{3}{c|}{\3}
                &\multicolumn{3}{c|}{\4}
                &\multicolumn{3}{c|}{\5}
                &\multicolumn{3}{c|}{\6}
                \\%
        \hline
        \hline
        \O &\1&\B&\R &\1&\O&\R &\3&\I&\L &\3&\O&\L &\4&\O&\L &\5&\B&\R&&&\\%
        \hline
        \I &\5&\B&\R &\2&\I&\R &\2&\I&\R &\3&\I&\L &\4&\B&\L &\5&\B&\R&&&\\%
        \hline
        \B &  &  &   &  &  &   &\4&\B&\L &\0&\B&\R &\6&\O&\R &\6&\B&\R&&&\\%
        \hline
        \end{tabular}%
}}

% tape
\textcolor{bTape}{\put(1,0){\makebox(0,0)[bl]{\rule{168mm}{10mm}}}}%
\textcolor{fSym}{\put(0,0){\line(1,0){170}}}%
\textcolor{fSym}{\put(0,10){\line(1,0){170}}}%
\textcolor{fSym}{\multiput(5,0)(10,0){17}{\line(0,1){10}}}%
\put(165,11){\makebox(0,0)[br]{\bf Tape}}%
% tape contents
\textcolor{fSym}{\put(  9,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put( 19,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put( 29,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put( 39,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put( 49,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put( 59,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put( 69,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put( 79,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put( 89,4){\makebox(0,0)[bl]{\I}}}%
\textcolor{fSym}{\put( 99,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put(109,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put(119,4){\makebox(0,0)[bl]{\O}}}%
\textcolor{fSym}{\put(129,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put(139,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put(149,4){\makebox(0,0)[bl]{\B}}}%
\textcolor{fSym}{\put(159,4){\makebox(0,0)[bl]{\B}}}%

% head
\put(40,18){\makebox(0,0)[br]{\bf R/W Head}}%
\put(34,14){\makebox(0,0)[r]{$\leftarrow$}}%
\put(46,14){\makebox(0,0)[l]{$\rightarrow$}}%
\textcolor{bHead}{\put(37,10.5){\makebox(0,0)[bl]{\rule{6mm}{2.5mm}}}}%
\textcolor{bHead}{\put(35,13){\makebox(0,0)[bl]{\rule{10mm}{4mm}}}}%
\thicklines%
\textcolor{bHead}{\put(40,13){\oval(7.0,2)[b]}}%
\textcolor{bHead}{\put(40,13){\oval(7.5,2)[b]}}%
\textcolor{bHead}{\put(40,13){\oval(8.0,3)[b]}}%
\textcolor{bHead}{\put(40,13){\oval(8.5,3)[b]}}%
\textcolor{bHead}{\put(40,13){\oval(9.0,4)[b]}}%
\textcolor{bHead}{\put(40,13){\oval(9.5,4)[b]}}%
\thinlines%
\textcolor{fDir}{\put(35,17){\line(1,0){10}}}%
\textcolor{fDir}{\put(35,13){\line(0,1){4}}}%
\textcolor{fDir}{\put(45,13){\line(0,1){4}}}%
\textcolor{fDir}{\put(40,13){\oval(10,5)[b]}}%
% cable fixed part
\thicklines%
\textcolor{fDir}{\put(90.000,36.000){\circle*{1}}}%
\textcolor{fDir}{\put(40.000,16.000){\circle*{1}}}%
\textcolor{fDir}{\put(90.000,36.000){\line(0,-1){5}}}%
% cable varying part
%\textcolor{fDir}{\put(90,31){\Line{40,16}}}%
\textcolor{fDir}{\put(90.000,31.000){\line(-3,-1){30.000}}%...
 \put(60.000,21.000){\line(-4,-1){20.000}}}%

\end{picture}
\end{document}

Lizenz

Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:

Diese Datei ist lizenziert unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international“.

Dieses Werk darf von dir

verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
neu zusammengestellt werden – abgewandelt und bearbeitet werden

Zu den folgenden Bedingungen:

Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.

Dateiversionen

Klicke auf einen Zeitpunkt, um diese Version zu laden.

	Version vom	Vorschaubild	Maße	Benutzer	Kommentar
aktuell	17:14, 20. Mär. 2019		1.033 × 441 (37 KB)	Jochen Burghardt	User created page with UploadWizard

Dateiverwendung

Keine Seiten verwenden diese Datei.

Metadaten

Diese Datei enthält weitere Informationen (beispielsweise Exif-Metadaten), die in der Regel von der Digitalkamera oder dem verwendeten Scanner stammen. Durch nachträgliche Bearbeitung der Originaldatei können einige Details verändert worden sein.

Software	TeX
Umwandlungsprogramm	pdfTeX-1.40.18
Verschlüsselt	no
Papierformat	496.06 x 212.597 pts
Version des PDF-Formats	1.5

Datei:MonusTuringMachine.pdf

Beschreibung

Lizenz

Kurzbeschreibungen

In dieser Datei abgebildete Objekte

Motiv

Urheber

Einige Werte ohne einen Wikidata-Eintrag

Urheberrechtsstatus

urheberrechtlich geschützt

Lizenz

Creative Commons Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 International

Datum der Gründung, Erstellung, Entstehung, Erbauung

20. März 2019

Quelle der Datei

durch Hochlader erstelltes Original

Dateiversionen

Dateiverwendung

Metadaten