How Computation Works (an Intuitive Approach)

[than3-bits]

Good Morning,

I just ran across this post, and have some suggestions I'd like to offer, if you would care to accept them. I'm an IT professional, having worked in IT roughly 10 years now.

While you touch on the individual components, the intuitive understanding is somewhat lacking/absent in your segments.

I'll briefly describe below what you should know, there is some technical vernacular but a rigorous understanding of these terms isn't necessary, nor do you need a lot of math; you should be able to get an intuitive understanding just from reading through this if you've completed Basic Algebra (which iirc is where they first provide the definition of a function).

At its core, a computer is a finite memory turing machine. It has a CPU which has an Instruction Set Architecture (ISA) that perform operations, and it is really quite simple for the amount of complexity it can reach emergently. The CPU using its instructions traverses the edges on a state graph.

At the signal domain level (closest to the hardware), for a computer to work and do work; you have to preserve certain system's/signal properties. There are several properties that a computer requires, some are hard requirements, and some are soft (i.e. you can get away with not having it in certain situations).

The hard properties are Determinism, and soft is Time Invariance (TI), and Memory-less (Memory violates TI). This is normally covered in an Intro to System's and Signal's course in an EE track college programs. System's and Signals by Oppenheim is the most well known text on the subject, but it takes a pedagogical approach to the bland subject by requiring rigorous math background to teach it eschewing some of the more common intuitions; for a reasonable understanding of computation it is not necessary aside from equivalences with function definitions. I've boiled down the important parts here.

Determinism, as a system property, is given a 'unique' set of inputs, you get a second 'unique' set of outputs (i.e. the mathematical definition of a function, each input has a 1:1 mapping to its outputs), this must hold true at each and every individual step of the state graph for the collection of inputs involved. Given digital system's only have a binary on or an off, there can only ever be one edge that traverses to the next state on the state graph (avoiding the decidability/undecidability problems).

Time Invariance, as a property, you perform the same function regardless of a shift in time and you get the same outputs given the same inputs used. This works hand in hand with Determinism.

Memory (soft), violates Time Invariance (i.e. this property is where you have caches present, where stale entries can occur and you must have the ability to flush those caches to troubleshoot).

What is important to remember is these properties are mostly preserved from bare metal all the way up through various abstraction layers... after the computing system has been brought up initially (i.e. Bringup, BUP in hardware speak).

You can violate these properties and they will remain violated (causing all sorts of silent issues, and undefined behavior), but not necessarily right away; its often chaotic. When the properties are preserved, they are closed under the operations (closure; Abstract Algebra really connects these concepts with regards to Sets), and how what computers do is really just math.

After BUP completes, the computer is constrained and keeps track of the current instruction it is currently handling, most of these instructions preserve these properties as well (i.e. to meet the unique input requirements). Reading data into an instruction and passing it into a program uses that data as an input. It must maintain that uniqueness (in a given context) to avoid undefined behavior.

There are times where the ISA instructions may not strictly preserve these properties, and when that happens there can be issues where you have to fall back on tests for these individual properties to classify potential problems, and potentially identify impossible to solve/measure directly issues.

At its core; The Determinism property, acts like a guard rail, for the CPU to follow, one instruction at a time, traveling along the state graph just like a train.

It only ever has one possible output given the same inputs for every instruction, and if you were to draw this out, it would looks like a heirarchical branch with only one possible choice at each step based on the inputs, and that runs up a hierarchical tree towards a root that it never gets to, and it does this without halting if there are no errors (for the most part).

This property is what makes a computer work in a nutshell.

There are a lot of individual technical component parts that need to come together, but without knowing what I've mentioned here, none of those parts can be combined and used intuitively, and it is often just a brittle memorization/rote understanding which is hard to remember. I'd err on the side of keeping these things simple.

You may also find there are some important insights to be had when viewing computer system's from a signal's property perspective.

For one, you'll find that troubleshooting a digital device becomes impossible when there are Memory properties that violate Time Invariance. Similar issues arise with Determinism being violated, where non-determinism may be injected at some point.

A non-deterministic problem as a class of problems may be chaotic, unpredictable, undefined behavior, and will be largely un-characterizable (you can't describe it or communicate it in any meaningful way to others, you often can't predict it), it may or may not be repeatable. These type of problems also are very difficult/impossible for error handling (outside coding in the entirety of acceptable input ranges for exception handling at each point in code), and may silently fail (where incorrect data is passed back after performing some work in an improper way).

You will know that when Determinism fails, (which can be tested by you), you can only rely on guess and check approaches for troubleshooting (in terms of time cost), and from the point that Determinism is violated, you'll know you can't pass it to a computer and have it perform work in a way that will provide a sound/valid results back (outside a very limited range of approximations).

What people do when they troubleshoot digital systems, is they perturb the system (at various points, by changing inputs), and it has an expected output that is probed. This foundation-ally relies on Determinism, and TI properties.

Doing this process at various points will allow you to isolate the section of the system where the problem occurs. It will let you know when hardware fails (because determinism is violated), this can come in many forms in software as well (most often at interfaces), some examples might be network address RFC 1918 conflicts, and a whole host of other related dependency problems based in the need for uniqueness.

Non-determinism issues as a problem class/failure domain will take orders of magnitude more time to track down and resolve in comparison to issues where determinism is present; since you only have a guess and check approach to identify the root cause. These classes of problem will also require intimate knowledge of the entirety of the system to fix.

There are a number of well established impossible to solve problems that computers cannot solve (under limits of computation), but in many cases you can restructure the problem so that computers can do work once certain constraints are put in place (determinism is one of the main constraints). This material is normally covered in an Automata Theory/Compiler Design course (i.e. The Dragon Book) in Computer Science/Engineering.

If there is one takeaway, it is that Determinism acts as the rail guard for a computer to actually do work. It also guards against the common problems such as halting, decidability, and undecidable problems. The definition of a function (in mathematics), and determinism is roughly equivalent (in a not so rigorous sense).

This is how all modern computers today (i.e. von Neumann Architecture) actually work.

For a nifty real-world example of a determinism problem in practice, on a linux system you can see non-determinism injection in the output of ldd against something like ssh. There are a few different ways this occurs, but the problematic one is the flattening behavior of the null state columns in the output. This is why you can't pass the ldd output to any kind of automation and have it work thereafter (it injects non-determinism). The whole point of automation is consistency and removing human error.

To correct it, you would have to patch the original output to not flatten/collapse columns with the null (empty column). You could try fuzzy matching to massage output, but it will break and is brittle depending on the inputs (the binary) that ldd is being run against.
It was reported in 2016, marked as not-a-bug; PaX forked them to fix it in 2018, mainstream repos today still have this marked as wont-fix.

Hopefully you've found this explanation useful.

[ILyesMk2]

Hi,

First i want to thank you for the amount of praiseworthy effort you put into explaining this.

Just so you know, the book's target audience is high schoolers/teenagers so my approach to the 'non-intuitive' explanation is half-done on purpose, which makes it easier to understand for complete beginners trying to have a low level perspective on their systems. If the reader didn't find the insight complex enough, they have the option to read deeper explanations made by people like you using the links i spread across the entire article.

For the deterministic part, IMO it's just an overly-stated concept that combines many many smaller pieces and attaches itself into the CPU. Once again, thanks i will look more into it (and possibly implement some of the info).
Cheers!