<p>Someone proved to me that even if the state machines are constrained to 2 states (i.e. 1 bit of memory) and there are only 2 possible inputs (i.e. 1 input bit), then for every single test, there is a finite state machine that could potentially detect a series of inputs that is different from the test.</p>
<p>The finite state machine could be constructed so that its internal state always defaults to a 0 but for every subsequent tick its internal state is 1. If the internal state is zero, and it's input is not the first input of the test, then it knows it knows it is receiving series of inputs other than that of the test.</p>
<p>There are three potential workarounds to this:</p>
<ul>
<li>Proving that no state machine can do this for a test is sufficient but not necessary to prove that a test is not cheat-able, so I could simply try a different way of proving it. There are other constraints to make this type of state machine impossible.*</li>
<li>I could use multiple distinct tests the reset the internal state in between tests. This is already done in other levels.</li>
<li>I could point out that a player would have to try to do that and the would not benefit from it in a way effecting their score, and then call it a day with this weaker definition of un-cheat-able.</li>
</ul>
<p>* Update: This has been shown to be possible within the constraints of the game as well, meaning I have to go with one of the other two work arounds.</p>

CC BY-SA 4.0
2022-06-27T06:38:18.510Z
1. I don't understand how this answers the question.  What is your answer to the question?  The first question is "Is it possible...?" so I would expect that an answer would begin "Yes because.." or "No because.."  2. What does "could potentially detect a series of inputs that is different from the test" mean?  3. What does "its internal state always defaults to a 0" mean?  Are you talking about the initial state / starting state?
D.W.
CC BY-SA 4.0
2022-05-27T23:24:29.987Z
2022-05-28T00:02:01.393Z
2022-05-28T00:02:01.393Z
Nic
<p>In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the previous inputs. The game tests if the circuit is correct by providing it with a test of (currently 14) inputs in a row and determines if the outputs are correct. I want find a test that I can prove can't be cheated (i.e. the only way to pass the test is to be a circuit that behaves correctly for all possible inputs).</p>
<p>Due to the constraints of the level the circuit can have no more than two bits of memory that are saved between ticks (i.e. clock cycles). When the circuit is initialized for the first input, the two bits of memory are set deterministically (i.e. they default to 0). I determined that to prove a set of test inputs is un-cheat-able, it is sufficient (even if overkill, due to other constraints of the level) to prove that there is no algorithm that can ever be sure that the series of inputs it has received is different from the test inputs with only two bits of memory in between each of the two bits of inputs. Since it is a more general problem, I figured this might already be solved.</p>
<p>Is it possible to construct a set of test inputs that can be proven to meet the condition? What is the smallest set of inputs that do? What if I managed change the problem to be three bits of inputs but only one bit of memory (by exploiting other constraints of the level)?</p>

CC BY-SA 4.0
2022-05-27T22:48:07.583Z
So I know now I am talking about finite state machines. There are a finite number of state machines with possible inputs and no more than 4 possible states. To solve the generalized problem I proposed I could use a computer to see if there is a state machine that always outputs a zero for the test but has a state/input combination where it outputs a 1. If there is not a state machine that does this, then my test is un-cheat-able. To solve the problem I originally set out to solve I could see if there is a state machine that passes the tests but is not the correct state machine.
Nic
CC BY-SA 4.0
2022-06-27T06:42:39.853Z
What can the tester observe?  What do you mean by "outputs"?  Do you mean that a test is a sequence of 2-bit inputs, and the tester can observe the outputs after each step in this sequence?  Or can only observe the final output?  Can the tester observe the memory of the circuit after each step in this sequence, or at the end?  Or only the 1-bit output?  Is the test a single sequence, or can you use multiple sequences / multiple tests?
D.W.
CC BY-SA 4.0
2022-06-27T06:45:50.567Z
What does it mean for a circuit to behave correctly?  Does correctness require that it produce the correct value for the memory, or only for the 1-bit output?
D.W.
<automata-theory><memory>
What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to know it is not being tested?
Nic
# What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to know it is not being tested?

(Asked by: username_0 on 2022-05-27)

In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the previous inputs. The game tests if the circuit is correct by providing it with a test of (currently 14) inputs in a row and determines if the outputs are correct. I want find a test that I can prove can't be cheated (i.e. the only way to pass the test is to be a circuit that behaves correctly for all possible inputs).

Due to the constraints of the level the circuit can have no more than two bits of memory that are saved between ticks (i.e. clock cycles). When the circuit is initialized for the first input, the two bits of memory are set deterministically (i.e. they default to 0). I determined that to prove a set of test inputs is un-cheat-able, it is sufficient (even if overkill, due to other constraints of the level) to prove that there is no algorithm that can ever be sure that the series of inputs it has received is different from the test inputs with only two bits of memory in between each of the two bits of inputs. Since it is a more general problem, I figured this might already be solved.

Is it possible to construct a set of test inputs that can be proven to meet the condition? What is the smallest set of inputs that do? What if I managed change the problem to be three bits of inputs but only one bit of memory (by exploiting other constraints of the level)?

**Tags:** automata-theory, memory

> **Comments:**
> **username_0**: So I know now I am talking about finite state machines. There are a finite number of state machines with possible inputs and no more than 4 possible states. To solve the generalized problem I proposed I could use a computer to see if there is a state machine that always outputs a zero for the test but has a state/input combination where it outputs a 1. If there is not a state machine that does this, then my test is un-cheat-able. To solve the problem I originally set out to solve I could see if there is a state machine that passes the tests but is not the correct state machine.  
> **username_1**: What can the tester observe?  What do you mean by "outputs"?  Do you mean that a test is a sequence of 2-bit inputs, and the tester can observe the outputs after each step in this sequence?  Or can only observe the final output?  Can the tester observe the memory of the circuit after each step in this sequence, or at the end?  Or only the 1-bit output?  Is the test a single sequence, or can you use multiple sequences / multiple tests?  
> **username_1**: What does it mean for a circuit to behave correctly?  Does correctness require that it produce the correct value for the memory, or only for the 1-bit output?  

---

## 1 answers

### Answer by username_0 on 2022-05-27. Score: 0

Someone proved to me that even if the state machines are constrained to 2 states (i.e. 1 bit of memory) and there are only 2 possible inputs (i.e. 1 input bit), then for every single test, there is a finite state machine that could potentially detect a series of inputs that is different from the test.

The finite state machine could be constructed so that its internal state always defaults to a 0 but for every subsequent tick its internal state is 1. If the internal state is zero, and it's input is not the first input of the test, then it knows it knows it is receiving series of inputs other than that of the test.

There are three potential workarounds to this:

* Proving that no state machine can do this for a test is sufficient but not necessary to prove that a test is not cheat-able, so I could simply try a different way of proving it. There are other constraints to make this type of state machine impossible.\*
* I could use multiple distinct tests the reset the internal state in between tests. This is already done in other levels.
* I could point out that a player would have to try to do that and the would not benefit from it in a way effecting their score, and then call it a day with this weaker definition of un-cheat-able.

\* Update: This has been shown to be possible within the constraints of the game as well, meaning I have to go with one of the other two work arounds.

> **Comments:**
> **username_1**: 1. I don't understand how this answers the question.  What is your answer to the question?  The first question is "Is it possible...?" so I would expect that an answer would begin "Yes because.." or "No because.."  2. What does "could potentially detect a series of inputs that is different from the test" mean?  3. What does "its internal state always defaults to a 0" mean?  Are you talking about the initial state / starting state?  

---

