Super Turing Computing
- Date published: 2026-11-06
- Speakers: Hava T. Siegelmann (guest talk to the Levin lab), with discussion with Michael Levin
- Format: Guest talk and discussion (51 min)
- Watch: https://www.youtube.com/watch?v=VX81ItGTnbo
- Topics: AI and biology, Control and energy, Cognition in cells
In one paragraph
Siegelmann presents "super Turing" computing as a foundation for ever-adapting, environment-aware systems. She starts from Alan Turing's 1936 model of a human calculator and shows that changing even one of its assumptions (discrete values, fixed deterministic rules, a fixed pre-written program) takes a system beyond the standard Turing model. She then describes classes of neural networks that she says are stronger than Turing machines, and the features she thinks matter for AI: learning from the input itself, continual updates, and effort that scales with the difficulty of the task. In the discussion Levin asks about the Church-Turing thesis and what a random coin adds to a small machine.
Main ideas (plain words)
- A standard Turing machine runs a fixed program on discrete symbols. She argues that real brains and nature differ on three points: physical (continuous) values instead of discrete ones, randomness, and programs that change through learning or evolution.
- She says changing any one of these is enough to leave the Turing world.
- A fourth route she likes: a series of Turing programs, each a little better than the last, that converge toward something beyond Turing. She says Turing himself suggested something along these lines, though he did not call it super Turing.
- She counts the possible input-to-output behaviours: a fixed program has "aleph zero" (countably infinite) options, a super Turing machine has two to the aleph zero, as many as the real numbers.
- She offers a half-joke built on that: the Turing test separates humans from the first kind of machine, and a "super Turing test" would be exponentially harder.
- Examples of stronger classes she describes: a small fixed network plus a biased coin whose bias carries information, and a small network that is given a short "advice" string depending on input length.
- Features she wants for future AI: (1) input can modify the program, not only the output; (2) continual updates from the environment instead of freezing parameters after training (she ties this to DARPA's lifelong learning work); (3) effort that scales with difficulty, as when driving a familiar road versus an icy one, instead of uniform energy on every step.
- In the discussion Levin asks what the Church-Turing thesis really claims. She says Turing never stated it and in fact wrote against it, that it is about engineered computers whose program you fully control and fix in advance, and that she does not see a claim about physically realizable machines in it. Asked whether the random coin must carry any information, she says she does not know the full answer: for a very particular behaviour you would probably need to know what to supply, but for generally capable behaviour, simply getting more random bits widens what a small machine can search.
Key quotes (word for word from YouTube's auto-generated captions)
"If you move from discrete to physical value we out of Turing."
https://www.youtube.com/watch?v=VX81ItGTnbo&t=954s"the super Turing test is really the test between human and two to the aleph zero."
https://www.youtube.com/watch?v=VX81ItGTnbo&t=1546s"But the program is fixed. In super turing, if you change the input, it may modify the program."
https://www.youtube.com/watch?v=VX81ItGTnbo&t=2108s"traditional computers they consume uniform energy on every clock cycle regardless of how the task is complex."
https://www.youtube.com/watch?v=VX81ItGTnbo&t=2310sSource: YouTube auto-generated captions, speakers not labeled; wording is provisional. Timestamps point to the start of the stretch that holds the quote, give or take a few seconds. All four quotes are the guest speaker.