Interview: The Dream of Thinking Machines

Interview Questions - The Dream of Thinking Machines

History questions in an AI interview are rarely about dates. They test whether you know which old results still constrain the systems you would build: what a machine can compute, what a behavioural test measures, and what testing can prove. Each answer below is written the way a well-prepared candidate would say it, followed by the point the question is probing.

Beginner

1. What is a Turing machine, and why does it matter to someone building software today?

It is Turing's 1936 definition of a mechanical procedure: a tape of cells, a head that reads and writes one cell and moves one step, a finite set of states, and a rule table that maps each state and symbol to a symbol to write, a move and a next state. A six-rule table is enough to add one to a binary number: walk right, turn at the blank, carry left. It matters because every program you write is equivalent to such a table, and because Turing used the model to prove limits that still apply to your code.

What the interviewer is checking: that you can describe the mechanism concretely, not just name it.

2. What was the imitation game, and has any machine passed it?

Turing proposed replacing "can machines think?" with a game: an interrogator types questions to two hidden parties and must tell which is the machine. He predicted that by about 2000 an average interrogator would have no more than a 70% chance of a right identification after five minutes. In Jones and Bergen's preregistered 2025 study, a persona-prompted GPT-4.5 was picked as the human in 73% of five-minute games, so interrogators were right about it only 27% of the time. By Turing's criterion, yes. But the same study had ELIZA at 23%, GPT-4o with minimal instructions at 21%, and GPT-4.5 itself at 36% once the persona prompt was removed, so the test measures convincing chat under specific conditions, not general intelligence.

What the interviewer is checking: that you can convert a win rate into the interrogator's accuracy and state what the result does not show.

3. Why do people still mention Ada Lovelace in AI discussions?

In her 1843 notes on Babbage's Analytical Engine she argued that a calculating machine could manipulate any symbols whose relationships can be expressed, not just numbers, and she published a table of operations for computing Bernoulli numbers; how the credit for that table divides between her and Babbage is still debated. She also wrote that the Engine "has no pretensions whatever to originate any thing", an objection Turing answered in 1950 by pointing to machines that learn.

What the interviewer is checking: accuracy about a contested claim, rather than repeating "first programmer" as settled fact.

Working Developer

4. Explain the halting problem and one consequence for code you ship.

No program can take an arbitrary program and input and always decide correctly whether it will finish. Rice's theorem extends that to any non-trivial property of what a program does. The consequence is practical: static analysers that promise to find every bug of some kind in every program must either restrict what they accept or report some false alarms or "don't know" answers. You cannot buy a tool that certifies an arbitrary script, including one an AI agent wrote, as harmless.

What the interviewer is checking: that you connect a theorem to tool limitations instead of treating it as trivia.

5. How would you build an XOR gate from threshold neurons, and why do you need more than one?

A single unit fires when w1·x1 + w2·x2 reaches a threshold. Silence on (0, 0) needs a positive threshold, firing on (0, 1) and (1, 0) needs each weight to reach it, and then (1, 1) reaches it too, so one unit cannot do XOR. Two layers can: one unit computes OR (weights 1 and 1, threshold 1), another NAND (weights −1 and −1, threshold −1.5), and a third ANDs them (weights 1 and 1, threshold 2). A brute-force search over 1,323 integer settings finds 14 of the 16 two-input functions and never XOR.

What the interviewer is checking: the proof, and the fact that depth, not just more units side by side, is what adds expressive power.

6. What is ELIZA's trick, and where do you see the same failure today?

ELIZA matched keywords with ranked rules, split the sentence around the keyword, swapped pronouns and slotted the pieces into a template, so "my boyfriend made me come here" became "YOUR BOYFRIEND MADE YOU COME HERE". The same rules turn "my gloop made me frimble" into an equally fluent echo. The failure was human: people read understanding into fluent replies. The modern version is trusting a language model's confident answer, which can be a hallucination. The defence is the same: test what the system knows on inputs it was not tuned on, and count results over many trials.

What the interviewer is checking: that you separate fluency from correctness and know how to test for the difference.

Senior Engineer

7. Your evaluation suite shows zero failures in 500 runs. What can you claim?

That the failure rate is probably low, not that it is zero. With zero failures in n independent runs the 95% upper bound is 1 − 0.05^(1/n), about 3/n: for 500 runs, 0.6%. If the product needs a failure rate under 0.1%, I need about 3,000 consecutive clean runs, and I need the runs to be independent, which means varied cases rather than 500 near-duplicates. SWE-bench Verified has exactly 500 tasks, so even a perfect score on it bounds the failure rate only below 0.6%.

What the interviewer is checking: statistical honesty about zero-failure results and awareness of independence.

8. When would you verify a component exhaustively instead of sampling its behaviour?

When its input space is small enough to enumerate. A rule over three yes/no facts has 8 cases, and a function of one 32-bit integer has 4.3 billion, which one machine can brute-force. A component that accepts free text or runs generated code has an input space far too large to enumerate: a 100-token prompt over a 128,256-token vocabulary has about 10⁵¹¹ possibilities. The answer flips at roughly the size of the test budget. Below it, check every case and state a proof; above it, restrict permissions and quote a sampled bound.

What the interviewer is checking: that you choose the kind of evidence by the size of the input space.

9. What did the 1955 Dartmouth proposal get wrong, and why should an engineer care?

Its conjecture, that every feature of intelligence can be described precisely enough for a machine to simulate it, set the research agenda. Its forecast, a significant advance on language use, abstraction and self-improvement from ten scientists in one summer, was off by decades. The engineering lesson is about estimates for open problems: the proposers knew the field better than anyone and still confused a clear problem statement with a near solution. I treat vendor roadmaps for unsolved capabilities the same way.

What the interviewer is checking: calibrated scepticism grounded in a documented case.

Architect

10. An AI agent will write and run scripts against the payments ledger. A risk committee asks you to prove it can never alter a paid transaction. What do you tell them?

That a general proof about the scripts is impossible, because by Rice's theorem no analyser decides behavioural properties of arbitrary programs. So I make the property true by construction: the agent runs with read-only credentials on the ledger and writes only to a staging table of proposed corrections, which a person approves. Then I bound what is left, the rate of wrong proposals, by sampling: about 300 clean runs rule out 1% at 95% confidence and about 3,000 rule out 0.1%. The committee gets a boundary plus a bound, which is the strongest honest evidence for a component that writes code.

What the interviewer is checking: that you replace an impossible guarantee with permissions and statistics, with the numbers.

11. A vendor demo shows its assistant chatting indistinguishably from a human. What evidence would you ask for before trusting it with customer-facing work?

A convincing conversation is Turing's test, and in 2025 GPT-4.5 passed it while ELIZA still fooled interrogators 23% of the time, so it tells me little about correctness. I would ask for task-level results on our own cases: accuracy on policy questions with known answers, behaviour on unanswerable and adversarial inputs, the failure rate with its sample size, and what the assistant is permitted to do when it is wrong. I would also ask how the result changes when the prompt changes: in that study the persona prompt alone moved GPT-4.5 from 36% to 73%, so a demo tells me about the demo's prompt as much as about the model.

What the interviewer is checking: that you distinguish behavioural impressiveness from measured task reliability.

12. Why does the stored-program idea still matter to AI system design?

Von Neumann's 1945 EDVAC report put instructions in the same memory as data, so programs can be loaded, modified and generated like any other data. That flexibility is what lets an agent write a script and run it, and it is also the root of a security problem: when instructions and data share a channel, data can masquerade as instructions. Prompt injection is the language-model version, where text the model reads is treated as instructions. Designs that keep untrusted data away from anything that can act, or that constrain what actions are possible, are the answer in both eras.

What the interviewer is checking: that you can trace a present-day risk back to an architectural choice and reason about the control.