Theoretical-Computer-Science

Sono variazioni possibili equivalenti: • Nastri addizionali • Testine addizionali • Nastri infiniti su entrambi i lati • Non-determinismo • Scelta probabilistica • Scelta quantistica Si può dire che la definizione di TM è stata robusta nella storia perché tantissimi formalismi che intuitivamente sembrano essere molto diversi rispetto alla TM alla fine possono essere dimostrate essere equivalenti. Turing con nastri addizionali Questo è presente in modo abbastanza facile sul Sipser. ...

Most of times the pattern of proving and verifying it is like this $prove \to verify$, that is: there is an entity that generates the solution, andPo then another that tries to verify it. But more expressive algorithms could be possible if there is interaction between the two entities, ones that try to prove it, and others try to verify it. From some point of view, this is similar from what AlphaGo does when searching, there is a part that guides the search, another that actually searches for it. Or the modern alpha geometry in modern times. ...

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. Simile al numero di Chaitin, che non è computabile, ma è approssimabile quanto si vuole. In un certo senso è computabile. The general idea is to ask how the function $\varphi$ that maps the longest $n$ proof to the number of steps of computation behaves. ...

This note is useful to gather in a single place the description of some common problems in CS and their theoretical implications explained in other notes. The Clique problem Description of the problem This problem is in NP, find all sub-graphs where all nodes are connected (this set of nodes forms a complete graph). We can prove that the problem is in NP because there is an easy non-deterministic algorithm that computes it. See Time and Space Complexity#Clique problem for details of this proof. ...

Intractable problems are solvable in principle, but in reality they require so much time or space that there no physical computers that can solve them in reasonable time. We would like to define a clear hierarchy of these set of problems. Space Hierarchies Def: Space constructible We say that a function $f: \mathbb{N} \to \mathbb{N}$ such that $f(n) \geq O(\log n)$ is space constructible if there exists a function from $1^{n} \to \langle f(n) \rangle$ is $O(f(n))$ space complexity. ...

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🟩 $$ x \in L' \iff f(x) \in L $$ This is very similar to the Halting Theorem and Reducibility#Mapping reducibility. The difference is that it needs to be polynomially-bounded, so to say, it is efficient function. ...

Halting theorem Questo è un problema fondamentale, che abbiamo trattato anche in Fondamenti teorica#Halting problem, ma qui lo ritrattiamo, perché così lo rifacciamo per bene. In parte è stato trattato anche al corso di Logica. Enunciato Halting theorem🟩 $$ HALT = \left\{ \langle x, y \rangle \in \Sigma^{*} \times \Sigma^{*}: x = code(M),M \text{ si ferma su } x\right\} $$Dimostrazione Halting theorem🟩 La parte del sì è facile perché basta eseguirlo e vedere che si ferma (quindi abbiamo una La macchina di Turing#La macchina di Turing universale. Se si ferma appartiene al linguaggio, altrimenti è la parte in cui diverge. ...

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). Però in questo campo si sono trovati molte concezioni equivalenti. Fino ad arrivare a concepire la tesi di Church-Turing. Il prof. nota che questo è strano, perché in altre discipline si converge in unico modello, mentre qui molte cose sono indifferenti. Questo è importante per capire come la concezione di Computer Science si è evoluta (Denning 2010). ...

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🟩 $$ L_{\mathcal{M}} = \left\{ x \in \Sigma^{*}: \mathcal{M} \text{ accetta } x \right\} $$$$ 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). Practically this definition is useful when we need to have a difference between the language and the Turing machine that decides that language. ...

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 $$ \mathbb{P}(b) = 2^{-k} $$ Where $k$ is the length of the branch. Then the probability of accepting the word is given by this: $$ \mathbb{P}(\mathcal{M} \text{ accepts } \omega) = \sum_{b \text{ is an accepting branch}} \mathbb{P}(b) $$ Note that this is very similar to the Algorithmic probability defined in Kolmogorov complexity. ...