#computing #ai #information #intelligence # [[Epistemic status]] #shower-thought # Universal [[Turing machine]] >If all this information, defining an automatic machine, were written out, it would form a ‘table of behaviour’ of a finite size. It would completely define the machine in the sense that whether physically constructed or not, the table would hold all the relevant information about it. From this abstract point of view, the table was the machine. >~ [[Turing]] ![[DALL·E 2022-06-27 20.23.20 - A fractalist cellular automata emerging into an unfriendly artificial intelligence, painting by Picasso.png]] A Universal Turing machine can execute all possible algorithms as a [[Turing machine]]. >In terms of [computational complexity](https://en.wikipedia.org/wiki/Computational_complexity_theory "Computational complexity theory"), a [multi-tape](https://en.wikipedia.org/wiki/Multitape_Turing_machine "Multitape Turing machine") universal Turing machine need only [be slower](https://en.wikipedia.org/wiki/Overhead_(computing) "Overhead (computing)") by [logarithmic](https://en.wikipedia.org/wiki/Logarithm "Logarithm") factor compared to the machines it simulates ![[Screenshot 2022-05-17 at 06.43.16.png]] >Another way to show that **Lisp was neater than Turing machines** was to write a universal Lisp function and show that it is briefer and more comprehensible than the description of a universal Turing machine. >~ [[Paul Graham]] > All you need is a third computer that, when given in input the numbers x and y and the command ‘Add’, sends them to the adder; whereas when it receives x and y and the command ‘Multiply’, sends those two inputs to the multiplier. Together, these three entities form a more general computer that can perform both addition and multiplication. Proceeding in this fashion, nothing stops you from imagining a computer that has all the physically possible computations in its repertoire. It is a universal computer: it can be programmed to perform any calculation that is physically allowed by certain physical laws. It so happens that the laws of physics of our universe do not forbid a universal computer. Computers such as our laptops and personal computers are universal in this sense > ~ [[Chiara Marletto - The Science of Can and Can't a Physicist's Journey Through the Land of Counterfactuals|Chiara Marletto]] Interoperability is a necessary property enabling the existence of universal Turing machines. >A universe where the interoperability property is violated would not have universal computers. This fact is a demonstration of how far-reaching the consequences of the interoperability of information can be. >~ [[Chiara Marletto - The Science of Can and Can't a Physicist's Journey Through the Land of Counterfactuals|Chiara Marletto]] ## In [[Cellular Automata]] ![[DALL·E 2022-06-27 20.23.32 - A fractalist cellular automata emerging into an unfriendly artificial intelligence, painting by Picasso.png]] https://arxiv.org/pdf/2110.14237.pdf https://distill.pub/2020/growing-ca/ https://towardsdatascience.com/cellular-automaton-and-deep-learning-2bf7c57139b3 <iframe width="560" height="315" src="https://www.youtube.com/embed/MDt2e8XtUcA?start=3929" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>