### What is computation? An introduction for humans

It occurs to me that in this age ruled by computers many people do not know what computation is.

If you feel you know what makes a computer "compute" you must be able to describe it no? What renders a lifeless collection of transistors and voltages into a working all emulating computer? If you cannot answer then your entire understanding of computers is completely spiritual and religious in my view - an entire practice of assuming (its not wrong its just not provably correct)! A simple experiment I always play on my non-Computer Scientist friends (perhaps very cruelly lol) is to ask them how a computer manages to check if two numbers are equal? "How do you write or design a machine that computes equality? Does it just magically calculate it as equal? How does it "weight" the numbers? Well how does it know the weights are the same?"

This illusively counter intuitive question brings to light the very underpinning of all logic on computers: equality and of course connectives.

Boolean logic that underpins computers is of course all built on this engine and this engine alone - is true equal to false? if not, then...   And if you are going to go absolutely bonkers trying to figure this out I suggest looking up the XOR operation (as far as i know - although if not true, entirely provable by construction) the XOR operation differences two numbers and returns the result - if they are the same the operation returns 0, if not it returns 1.

## What exactly did Turing do?

Alan Turing wrote down a description for computation. This description in modern times can be simplified in words (as far as I have studied it - having a degree in Computer Science, and many throughly wonderfully annoying friends in academia; annoying here being a compliment - you dare not speak incorrectly of what they dedicate almost their entire existences to understanding!) is this:

Computation is a series of state transitions of that can be labelled successfully using a set of symbols.
Formally speaking you need these ingredients in order to call a "thing" $M$ a proper thing that can compute or model computation, such a machine $M$ is capable of computation if this equality is possible:

$M = (Q, \Sigma, \delta, q_{0},F)$

Where the magic brackets here are to say "if you can call something a collection of these things" or "if you notice that something pulls together behaviors that can be described under one identity as these things..."; "these things" being the following:

• $Q$ - the set of states of the "computer" or machine, a seperable and finite set of behaviors it assumes under given conditions or stimulus, i.e. the thing that we call a machine, moves from this state to this one, and all these states we can collect in a finite set called $Q$!
• *notes for real geeks: $Q$ must be expressible as a set. With all the pitfalls of set-nesss including the horrid onslaught of cardinality vs ordinality  (I call this the cORDINAL sin of computation lol - the transition from cardinal sounding word to an ordinal sounding word echoing the very mistake itself). We need to be able to uphold provable arguments of membership testing in these sets. Essentially we are leveraging sets here because of Cantor 's work and because we need to be able to test and prove a computational state, as belonging to a given set- this is crucial otherwise you no longer have computation at all! Whatever institution of set or set-ness you use must have an engine that emulates set member testing laws and axioms, according to this definition!
• $q_{0}$ - the start state of the computer, this is a set of behaviour that can be said to be a kind of "ground state" or equilibrium (hay do we have any game theorists in the house? Nash to meet you!) of the computer - it always assumes this state before it begins accepting input. Or just before you give it input - it is always in this state.
• *notes for curious minds: You must ask yourself what makes the start state THE start state and not others; besides flimsy labelling? As far as I see it now (this might be horribly wrong naturally) - Of course you can call any state (I think chiefly because of how the $\epsilon$ or empty string is a member of every alphabet secretly being hidden by those Ghosts of set theory (https://en.m.wikipedia.org/wiki/Vacuous_truth) i ominously mentioned earlier ). But it helps to differentiate some start states or a given start state in order to define ordinality of course! - proof by construction (https://en.wikipedia.org/wiki/Constructive_proof ) for $q_{0}$ being a label attachable to any other and thereby producing the same equivalent machine $M^{'}$ could work in the form of "wrapping" (meaning we: construct a machine that processes input before it hits the actual machine $M$) in a machine $M^{'}$ that actually or emulatively reverses/reorders the symbols them as acceptable in the language of the original $M$. Off the cuff I don't see any objection to this, but i could be wrong! This might make an interesting exam question - possibly has in the past lol.
• $F$ the final or accept state is simply the one you would like to point at to say "ahh see its finished working". Possibly seen as another "equilibrium" state defined as the equilibrium reached after input is given always. This is a crucial state since it defines when a machine has accepted a given input or not - this state is essentially always assumed when the machine is done processing a given string.
• Same confusing questions as to what is the final state besides this labeling I think might apply here - of course you can ask what happens when you start doing monstrous things to a machine like:
• Making all the states final states?
• Making only a final state?
• Making the final state a set of states?
• Making the final state dependent on other states?
• Put it in different places call it different things etc - now you are doing real computer science! Possibly as horribly as I do it but none the less - WELCOME TO THE FOLD!
• $\Sigma$ - the alphabet of symbols, here it is another set but this is used to map the transition of one state to another, that is to say that you must be able to build a collection of symbols (doesn't matter at all what they are, as long as they preserve some form kind of semiotical differance) that label the machines transition from one state to others in the Q - so you must in a sense be able to point at all the behaviors of the machine and say "Ahh okay when it moves from this state in Q to that other state(s) in Q, i can represent this transition using a symbol in $\Sigma$ " if you cannot - you are in effect not looking at something not capable of computation at all.
• notes for geeks: Again we must invoke all the horrid ghosts of the sets - it is crucial we can test that elements are members of the set! Again if you label them; their labels are ordinal in value, if it is an infinite or provably infinite set of symbols - they loose their computational "value" and ordinality testing fails, since essentially infinite sets do not have ordinality. Example of this for non-mathematicians would be asking what the "first" integer is, given there are an finite amount both negative and positive; or perhaps if i were to spark a little fire in a mathematicians head reading this: what is the first number after 0.01? is it 0.001? or 0.000001 or 0.0000001? If you are logical enough you will realize there is no first one! Where does the number line "begin" if it is infinite in all directions? The answer is - it doesn't have a "beginning" in the sense that you can point a given member and say "here"; this is impossible - under its own infinite definition. This is a good thought game to play but be careful - many people think the inventor of this game drove himself mad with it - Cantor!  I think many people in software engineering and security are driving themselves mad with it today lol
• $\delta$ - The state transition function; this mapping of one symbol to the next; represents what happens when you "trip" the state of the machine with a given symbol and it moves to another state - i.e. this idea of "inputting" text into a machine happens according to these rules. We have above a set of the states $Q$ and a set of the symbols that represent strict enough changes in states $\Sigma$, but these two things alone don't have much value unless you have a " $\delta$ " of course functioning as the rules for associating strictly enough which symbols in $\Sigma$ correspond to the changes of states that go in $Q$ and always go in $Q$ , mathematically speaking:

$\delta ( q_{i} , w_{i} ) = q_{j}$
$\forall q_{i},q_{j} \in Q$ and $w_{i} \in \Sigma$

Which means if you have a machine defined under these rules then you must have this function that dictates what happens when:

The machine is in state $q_{i}$ from the set of all possible states $Q$ and given symbol say $w_{i}$ from the set of all possible symbols $\Sigma$; then $\delta$ says that the next state must and always must be the state $q_{j}$ that is also always from the set of all possible states $Q$.

We don't really care which specific states in this definition because it must apply to all possible state transitions; we don't even really care if $q_{i}$ and $q_{j}$ are always distinct*: it could be that the machine transitions to the same state upon certain inputs perhaps; but according to how I understand this (which is of course up for debate) - there must be at least one such differance enforcing state transition - or most importantly one such provable one!

*it is either an acceptable state of a special non-useful computer or a non-acceptable state of a computer: either way you will get a non-desirable state of computation - a computer that does not usefully compute according to how I mentally flesh this out. You might turn your imagination also to the other "possible" extreme - what happens when there are too many states? The machine also has no power in transitioning out of this single symbol alphabet - essentially it looses ordinality of its own states of computation.

You may have perhaps been hypnotized in modern times to think that this description is to be applied to only circuit boards or anything currently conceptualized as a computer. But consider that this definition existed before any modern form of computation, in fact as most Computer Scientists will tell you Computers as we know them were built by applying these ideas to a given purposed computation (finding german submarines, breaking comms encryption etc) - which then became consumable in a public form as the personal computer. What is written above; you should see as a kind of magical mystical (ironically actually demystifying also everything that is mysteriously seemed computational) recipe you can point at things and magically render them into computers instantly - should you be able to prove literally anything works according to this definition - and heres the real magic - can be argued under a given guise or perspective to work in such a way.

In terms of mathematically arguing this (according to my imagination) you could imagine having something that maybe is or maybe isn't a well behaving $\delta$, lets say it is some function $\omega$ (a "naughty" state transition function that misbehaves) - now to metaphorically argue or coax this $\omega$ into a good 'ol $delta$ you could wrap it or deconstruct it as such a function $\delta = \omega \circ Y$ where $Y$ is some function you pull all the outputs of omega through so it can be "forced" to take in and spit out (essentially "map") things in a way that behaves like an appreciable $delta$.

Here $Y$ in terms of Quantum computing could epynomogically (as in if it were named after someone then) be called the Yuri Manin https://en.wikipedia.org/wiki/Yuri_Manin function - as it renders hydrogen atoms under the function of Yuri's ideas - not changing the computational bed or behaviour in anyway but leveraging it through an interaction or "guise" or "lens" that allows us to employ the behaviour of the electrons as representing computation! Since all computers do is allow certain representations to point to a computational process or mechanism (this representation obviously requires us to spill into our own means of representing things - language!)

You now have a description of earnestly (and under rigorous mathematics of many of the greatest human - lol and non-human - minds to ever exist) what makes a computer "compute" - we know that functions can map things from one "realm" into another; all you need now is to go around constructing functions that map "non-computer" things into "computer" things to make them "compute"! Might seem like nonsense I agree; but this essentially what turned a set of voltage states into the computer you are using and what is currently turning electrons in the energy rungs of a hydrogen atom into a computer - and for all time and eternity will turn eventually (I think) the entire universe into one; after all we have turned what constitutes (as far as we know) the universe into computers itself. That is to say - we turned what makes the universe the universe into computation hosting "things" through quantum computing. What stops us from therefore *"Turing" literally everything in the universe into computers - both one massive one or a as compartmentalized sum of  "ones" either macro or microscopically? Nothing stops us nothing!

*(popular way i misspell "turning" as "Turing" here employed as an engine of expression like the computer itself - also a strong analogy of how language and its behaviour contributes to our interaction with computers! and of course misspelling is also a function of some kind! - nowadays folks are so caught up in their own perspectives you gotta explain all your jokes, luckily i find this funny too lol)