Input to program could be number of inputs, number of outputs, number of logic gates, and a circuit built up of logic gates... where the circuit does not have a loop, then finally test inputs to that circuit

Sample Input for one circuit test case might look like...

0 AND 1

2 AND 3

4 AND 5

Expected output for this circuit would be: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

4 -> Number of inputs, 1 -> Number of outputs, 3 -> number of logic gates. Logic gates in input would be referred by a numerical id. If there are I inputs to the circuit, then the id's 0 to I-1 would be reserved for the inputs. The next lines specify what inputs logic gate I takes in and what type of gate it is, then logic gate I+1, then logic gate I+2, etc.

That sounds cool! I remember thinking of something like this perhaps since years when I only studied programming, with Pascal.

There is one obstacle I see we need to think about, but on that later...

Even no need in limitation circuit does not have a loop. Loops are all right if we have clock input. Moreover this allows creating rather whimsical schematics - flip-flops, counters, adders, you know...

Thus the task is something like "implement logic interpreter". It can be extended, by the way, as the outputs of some expressions could be not the immediate outputs, but internal values, used in next level expressions:

0 AND 1 => Y1

2 AND 3 => Y2

4 AND 5 => T1

Y1 OR T1 => Y3

here Y... means the value of output while T... the internal value.

And "opposite" task we can have - to propose circuit for given set of inputs/outputs. E.g. like converting 4-bit input to seven-segment code. Though probably there could be found some ready generators...

Moreover to make things more fancy we can switch to some kind of ternary logic - need to research a bit about possible implementations :)

As about the difficulty I mentioned - it's just about generating some interesting examples for input - e.g. without trivial and redundand parts etc. Though possibly this can be achieved by randomly generating several examples and checking which is the "most beautiful" according to outputs.

I'll try to think about this - but if you have some ideas (or even would like to participate) - please share!

Ooh, your formulation of the problem is certainly more elegant. Better syntax on the input and the clock input is a good idea as well. If we're using Y for output, T for internal, I think we could also use I for input.

For generating interesting examples for inputs to the circuit generation problem... no idea :P

For the "opposite" task of proposing circuits some ideas could be

• A circuit which fetches or updates addressable memory

• Apply some encryption algorithm which uses simple operations (e.g. bitwise operations, maybe addition)

• Simulate a DFA

• Evaluate a SPECIFIC n degree polynomial (say, 1 <= n <= 8) for some integer x (say, 0 <= x <= 30) ... this is something I've thought of before and I've got a nice solution for it which doesn't require multiplication.

• Decode assembly instructions and send output signals that would be suitable for something like sending further instruction to the ALU or Registers or such

• Page Tables

• A circuit which takes in some pattern and sends out that pattern in a repeated fashion over time

  • e.g. the pattern could be 11001010, so at some starting time t it sends 1, then at t+1 it sends 1, at t+2 it sends 0, t+3 -> 0, t+4 -> 1, t+5 -> 0, t+6 -> 1, t+7-> 0, and then it loops.

• A circuit which tracks a 2D position and receives signals telling it to go N,W,S or E and reports its position

• Floating point number implementation that uses a small amount of bits for the exponent and mantissa.

  • From this video: https://youtu.be/5TFDG-y-EHs?t=510 I've heard that it's seemingly legal within the floating point specification to have a floating point number with 3 bits (1 for the sign, 1 for the exponent, 1 for the mantissa).

  • Though maybe we want more than that so we have a few more numbers than -inf, -1, -0, 0, 1, inf, and NAN :P

  • Not that we have to strictly abide by any spec, and can just define our own nonstandard floating point numbers.

I'm also imagining a "challenge problem" (one of those ones where there best solution is not necessarily obvious and you get more points for more optimal solution)... input is some complex circuit, output is supposed to be a simpler or faster version of the same circuit. Maybe some obvious inefficiencies can be baked in so there are some guaranteed improvements you can make, or you could start from a simpler circuit, and make it more complex by replacing some subsets of the logic gates to have the same truth table, but using more logic gates.

Fun fact btw, there is at least two simple algorithms to turn any truth table into a circuit (key terms: Conjunctive Normal Form, Disjunctive Normal Form). But of course the size of a truth table scales exponentially with the number of inputs, and the circuit produced is very likely not optimal... mainly just guarantees that a circuit is always possible given you fully know all possible inputs combinations and the corresponding outputs.