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:

1. Add the all-zero internal state to a queue.

2. 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.

3. 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. Nevertheless, this algorithm is very, very much infeasible.

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:

1. Add the all-zero internal state to a queue.

2. 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.

3. 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.

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. Detecting this in the general case is as hard as the Halting problem.

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.

You are wrong. The crux of sequential circuits is that they behave differently based on changing inputs over time. And we have infinite time.

Consider a one-to-one circuit that always returns 0, regardless of the input, unless the last $n$ inputs all have been $1$, where $n$ is an odd perfect number.

Now can you say whether this circuit is sequential or not? Doing so would be equivalent to (dis)proving a longstanding conjecture that there are no odd primes. We can construct harder examples where determining if the circuit is sequential is undecidable.

And since sequential circuits can ultimately emulate a turing machine, you can provide a proof in the usual self-referential style reducing to the halting problem.

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:

1. Add the all-zero internal state to a queue.

2. 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.

3. 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. Nevertheless, this algorithm is very, very much infeasible.