Ma dove/come? Nella lista dei linguaggi di programmazione conosciuti, tipo: C, Java, Python, $\LaTeX$... beh, sembra stonare un po'. Con un linguaggio di programmazione ci fai programmi, con il $\LaTeX$ no, ci scrivi e basta.
...
E invece no, il $\LaTeX$ è turing-completo.
Vale a dire: tutto quello che si può far fare a un computer, lo si può far fare programmando in $\LaTeX$.
Per dimostrarlo, è CNES (Condizione Necessaria E Sufficiente) simularci una Macchina di Turing.
Presto detto. Ecco il codice che soddisfa a tale proposito (ci vediamo sotto il codice):
turing.tex
1 % Copyright (c) 2012 the authors listed at the following URL, and/or
2 % the authors of referenced articles or incorporated external code:
3 % http://en.literateprograms.org/Turing_machine_simulator_(LaTeX)?action=history&offset=20070816200433
4 %
5 % Permission is hereby granted, free of charge, to any person obtaining
6 % a copy of this software and associated documentation files (the
7 % "Software"), to deal in the Software without restriction, including
8 % without limitation the rights to use, copy, modify, merge, publish,
9 % distribute, sublicense, and/or sell copies of the Software, and to
10 % permit persons to whom the Software is furnished to do so, subject to
11 % the following conditions:
12 %
13 % The above copyright notice and this permission notice shall be
14 % included in all copies or substantial portions of the Software.
15 %
16 % THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 % EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 % MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 % IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 % CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 % TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 % SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 %
24 % Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(LaTeX)?oldid=10889
25
26 \documentclass[12pt]{article}
27
28 \newcounter{headpos}
29 \setcounter{headpos}{0}
30
31 \newcommand{\Moveleft}{\addtocounter{headpos}{-1}%
32 moved one position to the \textbf{left}}
33 \newcommand{\Moveright}{\addtocounter{headpos}{1}%
34 moved one position to the \textbf{right}}
35
36 \newcommand{\ReadTape}[1]{%
37 \expandafter\let\expandafter\TapeAtHead\expandafter=%
38 \csname TapeAt\arabic{headpos}\endcsname%
39 \ifx\TapeAtHead\relax\expandafter\def\TapeAtHead{zero}\fi
40 \def#1{\TapeAtHead}
41 }
42
43 \newcommand{\Write}[1]{%
44 \expandafter\def\csname TapeAt\arabic{headpos}\endcsname{#1}%
45 wrote a \textbf{#1} at this position, }
46
47 \newcommand{\StateInitialText}{Initially the busy beaver was in state }
48
49 \newcounter{step}
50 \setcounter{step}{0}
51
52 \newcommand{\State}[1]{\ReadTape{\Symbol}%
53 \StateInitialText \textbf{#1}.%
54 \renewcommand{\StateInitialText}{and switched to state }
55
56 \addtocounter{step}{1}%
57 At the beginning of step \textbf{\arabic{step}}, the busy beaver was
58 in state \textbf{#1}, sitting at position \textbf{\arabic{headpos}}
59 of the tape. The tape at this position contained a \textbf{\Symbol}.
60 The beaver \csname#1\Symbol\endcsname}
61
62 \newcommand{\RunTuringMachine}{\State{A}}
63
64 \newcommand{\Azero}{\Write{one}\Moveright\State{B}}
65 \newcommand{\Aone}{\Write{one}\Moveleft\State{C}}
66 \newcommand{\Bzero}{\Write{one}\Moveleft\State{A}}
67 \newcommand{\Bone}{\Write{one}\Moveright\State{B}}
68 \newcommand{\Czero}{\Write{one}\Moveleft\State{B}}
69 \newcommand{\Cone}{\Write{one}\Moveleft\State{Halt}}
70
71 \newcommand{\Haltzero}{\Halt}
72 \newcommand{\Haltone}{\Halt}
73
74 \newcommand{\Halt}{stopped any activity.}
75
76
77
78 \begin{document}
79 \title{The Tale of the Busy Beaver}
80 \maketitle
81
82 \RunTuringMachine
83
84 \end{document}
Per quanto mi riguarda mi basta crederci, dato che capirlo richiede una conoscenza del $\LaTeX$ che non ho fretta di sviluppare stasera.
Per gli interessati la spiegazione è qui. Il sito, LiteratePrograms, da cui ho scopiazzato tutto, sarà tra l'altro sicuramente oggetto di future curiose incursioni.
No comments:
Post a Comment