Is there an algorithm to detect race conditions in logic circuits?
However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.


There are two different problems here. The simple solution (the one you should implement, in my opinion) is to simply look at the connection graph of the gates, and detect if the graph contains any cycles. If yes, simply reject the input.

The problem logisim refers to, which would amount to solving the halting problem, is one where you allow cycles, but reject sequential circuits.

This is different, because not every cycle in the graph affects the output, or worse, it affects the output but not in an sequential way.


  However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.


Initially I disagreed, but after some more thinking, I agree. Do note that we have infinite time here - we can supply infinite sequences of inputs to the circuit in an attempt to get sequential behavior.

Under the condition that we always let a circuit stabilize before changing the inputs (or rejecting the circuit as sequential in case it never stabilizes), a finite circuit is a finite state machine. The crux is that the output of the circuit depends on the input plus the internal state of every gate in the circuit.

To prove that a circuit is non-sequential you can use the following algorithm:


Add the all-zero internal state to a queue.
While the queue is not empty, pop an internal state from the queue and construct the truth table for all inputs using that initial internal state. Also add the internal state to some set tracking internal states we have handled. For each internal state reached from this internal state while computing the truth table, add it to the queue if it's not inside our handled set.
If at any point in 2 a circuit does not stabilize, return sequential. If at any point during 2 the generated truth table does not equate the one from the all-zero internal state, return sequential. Otherwise return non-sequential.


Since there are a finite amount of possible internal states, this algorithm always terminates. And it fully explores all reachable states. Nevertheless, this algorithm is very, very much infeasible.