# P3768: Largest preset distinguishing length for an eight-state binary Mealy machine

- ID: `P3768`
- Reference: `mealy-eight-preset-distinguishing`
- Page: https://theoremdb.org/statements/P3768
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: f295905458d7a3b058de2e38a46a52071c41c31e
- Current Markdown: https://api.theoremdb.org/v1/statements/mealy-eight-preset-distinguishing?representation=markdown
- Record maturity: Reviewed problem

## The problem

Among complete \(8\)-state Mealy machines with binary input and output alphabets that admit a preset distinguishing sequence, determine the largest possible length of a shortest such sequence.

### Remarks

- **Remark.** A preset distinguishing sequence is one fixed input word whose eight output words, one for each possible initial state, are pairwise distinct.
- **Remark.** Machines with equivalent states or with no preset distinguishing sequence are excluded.
- **Remark.** Sequence length counts input symbols.

### What counts as a solution

- Give an eligible machine whose shortest preset sequence has length L and a complete normalized machine census or theorem proving every eligible machine has one of length at most L.

## Status

**Resolution status:** Open.

No proof or formalization has been recorded.

## Research packet

### Background and intake notes

The outer family is finite, and each candidate's shortest length has a compact partition-refinement trace.

- For one machine, breadth-first search over partitions of initial states proves the shortest preset word.
- Quotient machines by state relabeling, input swap, and output complementation before the outer search.
- Adaptive distinguishing trees optimize a different resource and can exist when no preset word does.

- Recorded example: A cyclic machine already needs a length-seven word to distinguish all eight starts.

### Computational notes

- For the example, input 0 advances i to i+1 modulo 8 and outputs one exactly when the old state is 0; input 1 fixes every state and outputs zero. The word 0000000 yields seven distinct one-hot output positions plus the all-zero word, and exhaustive prefix checking proves no shorter word distinguishes eight states.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `mealy-eight-preset-distinguishing`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.