Sunday, February 12, 2012

Il $\LaTeX$ è un linguaggio di programmazione in piena regola

Tempo fa nel ritrovarmi a stendere il mio curriculum sorse un dubbio che non tardò poi a ripetersi in analoghe situazioni di conoscenti. Arrivati alle competenze informatiche, si faceva il momento di dover dire "ok, so scrivere in $\LaTeX$".
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.  

Friday, February 10, 2012

Macchina di Turing minimale

Sia $T$ una macchina di Turing e sia $<x_i,q_i,q_o,x_o,m>$ una sua quintupla.
Mostriamo che è possibile costruire una macchina di Turing $T_{triple}$ per la quale esista un insieme di triple che, per ogni singola quintupla di $T$, ne simula il comportamento (ovvero dati $x_i$ e $q_i$, stamperà $x_o$ e farà passare la macchina nello stato $q_o$, muovendo la testina in accordo a $m$); tali triple sono della forma $<x,q,y>$ dove $y$ è
  1. il simbolo da scrivere al posto di $x$, se $y$ appartiene all'alfabeato;
  2. il nuovo stato cui la macchina passa, lasciando lo stato $q$, se $y$ appartiene all'insieme degli stati;
  3. il movimento da compiere, se $y$ appartiene all'insieme dei movimenti (destra oppure sinistra).
Per maggiore chiarezza, consideriamo un numero di triple maggiore del necessario.
Riportiamo tali triple e successivamente le discutiamo.
  1.  $<x_i,q_i,(q_o^m,x_o^m)>$ per ogni input e stato privi di apice, dove $(q_o^m,x_o^m)$  appartiene all'insieme degli stati di $T_{triple}$;
  2.  $<x_i,(q_o^m,x_o^m),x_o^m>$ per ogni input letto diverso dal simbolo $x$ contenuto in $(q,x)$;
  3.  $<x_o^m,(q_o^m,x_o^m),q_o^m>$ se l'input letto eguaglia il simbolo $x$ contenuto in $(q,x)$;
  4.  $<x_o^m,q_o^m,m>$ se gli apici $m$ dell'input e dello stato sono uguali.
  5.  $<x^m,q^{m'},(q,x)>$ \textbf{se gli apici dell'input e dello stato sono diversi.}
  6.  $<x,q^{m},(q,x)>$ \textbf{se l'input non ha apice e lo stato sì.}
Studiamo la correttezza della precedente costruzione.
L'alfabeto di $T$ è stato esteso in modo che tutti i simboli contengano due copie di sé , date dal medesimo simbolo con in apice uno dei due movimenti.
L'insieme degli stati di $T$ è stato esteso come quello dell'alfabeto e, inoltre, aggiungendo tutte le
triple date dagli ultimi tre simboli di ogni quintupla nell'insieme delle quintuple di $T$.
Ragioniamo ora, senza perdere di generalità, nel caso in cui $T$ sia deterministica, e dunque l'insieme delle quintuple definisca, a partire dalla coppia input-statoAttuale, la tripla nuovoStato-output-movimento in maniera univoca (in accordo alla formalizzazione data da Ullman e Hopcroft).
  1.  Letto il simbolo $x_i$ nello stato $q_i$ pertanto si passerà ad un univocamente identificato stato del tipo $(q_o^m,x_o^m)$;
  2. a questo punto la seconda tripla imporrà che l'output su nastro sia quello originariamente voluto dalla macchina $T$ (con l'aggiunta del simbolo del movimento da effettuare in apice);
  3. successivamente la terza tripla imporrà che anche il nuovo stato sia quello originariamente voluto dalla macchina $T$ (con l'aggiunta, anche qui, del simbolo del movimento da effettuare in apice);
  4. nel momento in cui la macchina legge un input che ha in apice lo stesso simbolo di movimento in apice al proprio stato, compie tale movimento;
  5. \textbf{notiamo che sarebbe desiderabile, a scanso di errori, che andandosene dalla cella del nastro in esame la macchina abbia esattamente lo stesso stato e lasci scritto esattamente lo stesso simbolo previsti dalla originaria quintupla. Questo obiettivo viene raggiunto qualora la testina ritorni su tale cella, poiché, nel tornare, lo stato della macchina avrà in apice un simbolo di movimento opposto a quello del simbolo che la testina leggerà} (se "se n'è andata" verso destra, dovrà tornare da sinistra, e viceversa) ; in tal caso la tripla numero 5, assieme alla tripla 2 e 3, riscriverà in maniera ben definita l'input e cambierà lo stato privandoli dell'apice di movimento, e la tripla 1 potrà avere luogo secondo quanto già descritto;
  6. nella quintupla la testina si muove dopo che la macchina è passata nello stato $q_o$; pertanto quest'ultima tripla, assieme alla precedente, assicura che spostarsi essendo nello stato $q_o^m$ non creerà problemi.

Wednesday, February 8, 2012

Parentele esponenziali

Forse per molti amanti dei pranzi e cene coi parenti, questa non è proprio un'allegra constatazione... 
ma chi non c'ha mai pensato?

Monday, February 6, 2012

Più matematica per tutti


Suggerendo l'articolo How to learn to love maths...
Maths is justified in this country because it is useful. Sparks said his proposals were necessary because young people need a better grasp of maths to compete in the job market, where an understanding of technology and numeracy are increasingly important.
 I agree. But maths should also be studied for the same reasons we study Shakespeare – it is our intellectual and cultural heritage. Maths makes us more creative and gives us a deeper understanding of the way things really are.

Saturday, February 4, 2012

That’s why I only fall in love with dots.

Colgo l'occasione per segnalare i migliori due siti che finora ho trovato di "cazzeggio matematico", Math Fail e Math-Frolic!.
That’s why I only fall in love with dots.


Thursday, February 2, 2012

LATEKnica

Pare spesso un'epopea usare il $\LaTeX$ in Blogger... così sbarco al nuovo trick, che pare affidabile...

To enable MathJax, just drop in
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js">MathJax.Hub.Config({ extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: {     inlineMath: [ ['$','$'], ["\\(","\\)"] ],     displayMath: [ ['$$','$$'], ["\\[","\\]"] ], }, "HTML-CSS": { availableFonts: ["TeX"] }});</script>
after the header (<head>) in the Blogger template (Design→Edit HTML→Edit Template).

$:)$