weighted graph
Is it possible to make a UTC that's a weighted graph of some type, containing only one type of node?
Loops would be implemented via cyclical graphs, but they could be terminated because a cycle could stop once the signal transferred falls to 0 or below a certain threshold, or perhaps acquires a halt key somehow.
An ideal form of this computer might actually be analog, thus making this a digital simulation of an analog computer, and maybe even allowing it to approximate huperturing solutions that can only be executed by analog machines.
However, the computer could still be used to do binary operations explicitly by using weights of 0 and 1, or maybe by using only integer values.
One possible addition to the language would be to allow it to modify its own network, but I would avoid doing so unless it simplifies the task of making it Turing-complete.
Obviously, the three ways it could modify itself are:
Changing weight values
Making and breaking connections
Creating and deleting nodes (we probably shouldn't allow deleting any nodes that have remaining connections to them, but nor do we want to delete a node automatically that has no remaining connections, because then we can't reconnect it later.. unless, of course, by the definition of the graph there is no way to refer to a node other than via a path to it, in which case that also implies that a node cannot be created without simultaneously connecting to it.)
If there are different types of nodes (*balk..*), then changing a node's type can also be another way of self-modifying.
Another possible method would be switching/copying one node/weight for another. But that's probably superfluous and probably hardly useful at all. Come to think of it, we could delete, move, transpose, copy, etc. entire portions of the graph too if we want.
It might be possible, though very inefficient, to preserve the exact values of all multiplications (and whatever other operations) that a signal undergoes throughout the program, by storing values in terms of unlimited-length continued fractions or ratios of two unlimited-length bignums, and/or arbitrary mathematical expressions (maybe even including the transcendental). This of course makes it still not analog, because no original input signal can have an infinite amount of precision. How that limits any of its theoretical ability I don't know, because there'd be no use for an infinitely precise input to a computer anyway.
Principles from what's known as "influence diagrams" could possibly be useful for specifying this language.
A possible methodology for coming up with the minimal turing-complete spec:
Start with a useful algorithm or program
Separate it into separate functions as much as possible connected only by connections between nodes on the graph (hopefully we can factor any loop structures out of the code blocks themselves.)
Analyze each unit function remaining and see how they can be further separated into sub-functions connected by the graph
Goto step 3
Do this until you come to the minimal possible instruction set for defining the behaviors of nodes. Note that even a UTC can support a single instruction with a single operand, so we need to factor out a complete capability from the language, such as the ability to jump, the ability to access more than x memory locations, the ability to write to/read from memory at all, the ability to nest expressions, the ability to write subclauses/functions, if conditions, the ability to write commands in sequence, the ability to write more than one command or expression, the ability to halt, the ability not to halt, etc.
(We don't want to make our individual node capabilities Turing-complete, because otherwise the whole facet of having nodes and connections is theoretically superfluous.)