Would a state machine in 3 dimensions be the same as combinational logic in 4 dimensions?

Question

Suppose you take a state machine(a machine who's output is dependant on its inputs and the internal state of the machine) and take the dimension of time and turn it into a 4th spacial dimension, would we then have a 4 dimensional combinational machine(a machine whos outputs are only dependant on its inputs)?

I've always pondered wether time could be viewed as a fourth spacial dimension, if there was anything unique about time that made it different from the other spacial dimensions. Wether we, as humans just percieve it differently.

Answer 1

What a strange question...

I would say

NO!

and here is why:

A state machine is a purely mathematical concept that uses neither the notion of space or time, therefor it is independent of any physical implementation.

And even if you went at the problem from a thermodynamic/information theoretical perspective for physical implementations of state machines, naively I would have to say that because a state machine stores information while combinatorial logic does not, the entropy associated with the two systems would have to be different.

I said naively... which means I am waiting to be proven wrong by someone who has done the math rather than giving a hand waveing argument.

Now... I suppose there is a second interpretation of your question, which stays completely in the realm of abstract math, which is probably:

"Can one unfold a state machine into a purely combinatorial representation?"

And the answer to that would be, yes, one can. One way you do it is by removing the internal state and by making it a second set of inputs. This is equivalent to formulating the

s sub n+1 = f sub SM(s sub n, x sub n)

feedback as a recursive function

s sub n+1 = f sub SM(y sub s, x sub n),

where y sub n is f sub SM(y sub n-1, x sub n-1) etc. and ultimately y sub 0 becomes the initial state s sub initial.

So at any given moment, the output of the state machine is a mapping from the s sub initial state and all external states x sub i=0..n which happened between the initial state and the current state.

For a non-trivial state machine this recursive function can be enormously complex! In practice the computational complexity to calculate that function is most likely an NP complete problem, although, for special machines like counters etc., you can pre-compute the output easily. Advanced digital simulators/design provers do these things on the fly to save time (let's say you need to simulate a 32 bit counter... would you make 2^32 steps through the simulator or rather just use the clock cycle counter to represent the output at any given time?).

Hope this gives some food for thought.

Answer 2

It may or may not be, it depends on whether or not the system is a single ergodic system. It would also be relevant if the system could be formulated as a Lie Algebra and follow the Noether Theorem for symmetry. Why do you ask?

One can mathematically create any space-time model, one wishes. 1 time and 3 spatial dimensions. 2 time and 3 spatial dimensions, 3 time and 3 spatial dimensions etc. etc. Whether any of these systems correspond to "reality" and how they correspond is the essential question as to judging their usefulness. The symmetrical ones are the most promising ones so far study. Ergodic systems where the spatial averages equal the long term time averages might be the system you are seeking. It is difficult to say without specifics.