I'm writing a logic gate simulator. I would like to prevent user from constructing circuits prone to race condition such as flip-flops, and instead provide them as separate building blocks. Is that possible?
edit: I've got an idea. I guess that race conditions can only arise from logic circuit outputs directly or indirectly affecting their own inputs. So one way to check their validity would be to compare the truth tables of their inputs and outputs.
example one: NOT gate feeding itself
A = !A A | A A | !A --+-- ---+--- T | T T | F F | F F | T the truth tables do not match!
example two: SR NOR latch
!(A || B) = C !(C || D) = B !((!(A || B)) || D) = B // C => !(A || B) A | B | D | !((!(A || B)) || D) B | B ---+---+---+-------------------- ---+--- F | F | F | F F | F F | F | T | F F | F F | T | F | T T | T F | T | T | F (wrong!) T | T T | F | F | T (wrong!) F | F T | F | T | F F | F T | T | F | T T | T T | T | T | F (wrong!) T | T
I hope you understand what I'm trying to convey. However, I have nothing to back it up, and I struggle to define it into an algorithm, and even if I could, it would have horrible complexity. I will try to refine it tommorow.
edit 2: this is what I found in logisim manual:
Logisim will not attempt to detect sequential circuits: If you tell it to analyze a sequential circuit, it will still create a truth table and corresponding Boolean expressions, although these will not accurately summarize the circuit behavior. (In fact, detecting sequential circuits is provably impossible, as it would amount to solving the Halting Problem. Of course, you might hope that Logisim would make at least some attempt - perhaps look for flip-flops or cycles in the wires - but it does not.) As a result, the Combinational Analysis system should not be used indiscriminately: Only use it when you are indeed sure that the circuit you are analyzing is indeed combinational!
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.