Theoretical-Computer-Science

Introduzione Note filosofiche (non impo) Bisogna in primo momento cercare di definire cosa è la computazione e cosa è un computer. Aristotele faceva la distinzione fra proprietà essenziali e accidentali. Quelle essenziali sono proprie dell’oggetto. Una sedia può essere fatta di legno o di metallo, ma questa proprietà è accidentale, ovvero, essa rimane una sedia indipendentemente dal materiale di cui è fatta. Solitamente in matematica si prova ad astrarre (vedi Astrazione sul controllo per nota generale sull’astrazione)....

Cook Levin theorem is important because says that in 1971 if $SAT \in P$ then $NP = P$. We will start with this idea to define the concept of NP-completeness. Let’s start with the basics. Poly-reduction Def: poly-reduction🟩 We say that two languages $L$ and $L'$ defines over alphabet $\Sigma$. We say that $L´$ is poly (mapping)-reducible in $L$, $L' \leq_{p} L$ when a $TM$ that computes polynomial time a function $f: \Sigma^{*} \to \Sigma^{*}$ such that $$ x \in L' \iff f(x) \in L $$ This is very similar to the Halting Theorem and Reducibility#Mapping reducibility....

Introduction to the Rice Theorem Ci sono molti teoremi che non possono essere decisi, vedere Halting Theorem and Reducibility. Qui andiamo a chiederci quale sia l’insieme dei problemi decidibili. Proprietà dei linguaggi TM🟩 Data una macchina $\mathcal{M}$ definiamo il suo linguaggio come $$ L_{\mathcal{M}} = \left\{ x \in \Sigma^{*}: \mathcal{M} \text{ accetta } x \right\} $$ Allora con questa definizione di linguaggio possiamo dire che una proprietà, ossia una funzione da tutti i $TM$ possibili a $\left\{ 0, 1 \right\}$ tale per cui se il linguaggio riconosciuto è lo stesso, ossia $$ L_{\mathcal{M}} = L_{\mathcal{M}'} \implies P(\mathcal{M}) = P(\mathcal{M}') $$ Definiamo questa non triviale se esiste una macchina per cui è 0, e una per cui è 1 (ossia non è costante)....

Introduction to the probabilistic Turing Machine Most of real phenomena are better comprehended by a probabilistic view. This pushes to build a formal model that takes probability into account Def: Probabilistic TM Take a non deterministic TM La macchina di Turing. At each step there is a fair coin-flip that has two legal branches. So the probability of a certain branch is $$ \mathbb{P}(b) = 2^{-k} $$ Where $k$ is the length of the branch....

In this note we explore a theme of time and space complexity. Those are cardinal themes in Theoretical CS. Time -> execution step bounds on algorithms Space -> the cells visited by a Turing Machine when executed. Introduction to Time Complexity This note will build upon know techniques of algorithms analysis explained in Notazione Asintotica. We will need big-$O$ notation and $o$ notation. L’idea è che il problema di decisione è decidibile se limito la lunghezza del teorema....