Is there a notion of an infinite "Rado graph-like" random algorithm?

Question

Disclaimer before starting: I'm not using "algorithm" in the usual sense, but I don't know what the right term for what I'm talking about is, if there even is one. Here, "algorithms" do not necessarily have a finite amount of instructions, and do not necessarily terminate. I know about Turing Machines, and it's probably equivalent to Turing Machines, only I'm not using any formal definition. As such, the description of the problem and the question will be very informal, and possibly flawed and/or inconsistent, the reason being that I'm asking if something "similar to that" but formalized exists, starting from a naive idea.

Motivation and context

After learning about the Rado graph, I wondered if such a thing existed for algorithms: an algorithm that does not necessarily terminate but that "embeds" an equivalent of every other algorithm (including those that don't terminate), more on that later. The reason behind the question is not mathematical but rather a philosophical itch (exploring the possible implications of the mathematical universe hypothesis).

Possibly among other things, this algorithm $U$ would have a set of variables $X$, and steps would still be numbered sequentially. What I meant earlier by "embed" is that for any (possibly unending) algorithm $a$ with specific inputs, you can find a subset $Y \subset X$ of variables, and a subset $A\subset \mathbb{N}$ such that the algorithm only acts on the variables of $Y$ at precisely the steps in set $A$ (I'll shorten that to "at steps $A$" let me know if this is confusing, I'll edit), such that if you looked only at the variables from $Y$ at steps $A$, it would look like you are running $a$ with those specific inputs.

This is the rough idea. Now I'm aware that this naive idea already has obvious problems with it (mainly due to it not being formalized, and not being restricted enough) :

• I haven't defined what type of instructions could steps entail or correspond to.
• I haven't defined what kind of values the variables could take or be initialized with, which is a problem since for instance even a simple "algorithm" that at each step adds $1$ to a single variable, indefinitely, could be defined for any real number, which instantly makes the premise of the algorithm impossible because of a cardinality issue. A possible solution to that would be to restrict values to those that can be reached from natural numbers and a finite amount of instructions using a finite amount of variables. Obviously, this still is a downgrade from the initial, even more naive idea of "including every algorithms with every inputs", since now the inputs are restricted, but this is inevitable.

I'm already sure about the answers to (1) and (2), but the questions are:

(1) Is there something "kind of like this" which is a thing whose properties were studied? Possibly a Turing machine.

(2) Is there anything interesting about it? Is it anything more than just "all (not actually all) algorithms running in parallel, that's it"?

(3) Is there an alternative concept that could have interesting properties? By alternative concept I mean an idea that might differ on several points but is still close to the spirit of topic, i.e. one that would fit for the title question, that has a property even vaguely, very remotely similar to that of the Rado graph's extension property

(4) If the answer to (3) is "yes", what is it, what what interesting properties does it have?

I assume the answer to (1) is yes, and it'd be through some Turing machine. The answer to (2) is most definitely "no", since because of the way it was defined, "sub-algorithms" are pretty much self contained and their variables remain isolated from the rest, whereas in the Rado graph, every vertex is pretty much garanteed to be connected to an infinite amount of other nodes.

I am also unsure what to tag this.

Edit : removed "If the answer to (2) is no" from question (3).

Answer 1

I would argue that this is exactly the right way to think about a universal Turing machine.

For simplicity, let's shift attention from algorithms to (partial) functions computed by those algorithms. It turns out that there is a binary function $U(x,y)$ with the following properties:

• $U$ is computable (in the Turing machine sense).

• For every computable unary partial function $f$ there is some $n$ such that $f(x)\simeq U(x,n).$

• In fact, $U$ satisfies the even stronger property that for every computable binary partial function $g(x,y)$ there is a total computable $t$ such that $g(x,y)\simeq f(x, t(y)).$

This turns out to be the right definition of a universal computable (binary) function. The point I want to make here is that the third clause above doesn't just strengthen the second clause and rule out some pathologies (see here), it also corresponds more accurately to the universal embedding property of the Rado graph: the objects being compared are the binary partial computable functions, and the third bulletpoint above says that we have the desired embedding property.