- If the audience if programmers unfamiliar with automata theory, I am not sure how many would know what a Turing machine, von Neumann machine, or even a program counter is.
- Clarifying what is meant by "internal" and "external" state.
There is an instruction pointer. Note that it doesn't count. It frequently is incremented, but it can jump forward and even backward. It points at an instruction.
[1] Technically, until you get to the 64-bit version, it's `CS:IP` (Code Segment, Instruction Pointer).
The register is always an instruction pointer, even if the hardware incorrectly calls it a program counter.
The processor that matters most, by far, is x86. At one point PowerPC wasn't too far behind, and PowerPC still dominates in high-end network gear. Both of these processors are correctly documented. For x86 the name is ip, eip, or rip. For PowerPC the name is usually nip, meaning "next instruction pointer". Sometimes the PowerPC documentation will use "current" instead of "next", or "address" instead of "pointer". All of these are correct.
Also, in electrical engineering, the direction of electricity is taught backwards from what it really does. In all sources I've read, electricity flows from positive to ground, whereas in reality, it's the opposite. Good luck in changing that.
And again, you want to be aware that you are going to have sharply different experiences depending upon the candidate's familiarity with the basic research.
It would be very interesting to walk through a candidate's thinking about this problem "raw," but it would be grossly unfair to ask the same question of an intern who had studied the problem in the last semester.
I have seen interview questions along the lines of "reinvent basic research," but they typically pick something obscure-ish to reduce the likelihood that the candidate has seen it before, and such things are usually more of the dreaded "whiteboard your thinking," rather than judging you based on the code produced.
> Outside of a special-case like certain CS students, this question is likely to give very inconsistent results, and those results are going to be dominated by a candidate’s recent familiarity with the underlying problem, rather than their coding skills.
> In most cases, that makes for a bad interview question.
This only makes it a bad interview question if the goal of the question is to only hire the candidates that can code the solution.
Otherwise, it can be a very good interview question. How do they go about "reinvent[ing] the basic research of people like Kleene and von Dyck, extemporaneously"? What questions do they ask? What ideas do they come up with? What resources do they say they would consult? Under pressure, how do they behave? If they make a mistake, are they coachable? Do they lash out or double-down on mistakes? If they mention using a language's regex, do they understand the performance tradeoffs of various different features?
There is a lot to see by asking the question beyond just "whether or not candidate X can code a solution".