(Some of what I say here isn't technically accurate; i.e., it's "close to the right idea but technically wrong". Parent asked for a layperson's explanation.)
There's a famous problem in CS called the halting problem. The halting problem asks for a program that tells you whether an arbitrary program (turning machine) ever halts (a.k.a. stops executing). A function that could compute a solution to the halting problem is called a halting function.
Turning machines can't compute a solution to the halting problem.
Therefore, if you add an oracle for the halting problem to an otherwise normal turing machine, then the resulting model of computation is stronger than turing machines alone. And oracle is basically a magical box that answers your questions in O(1) time, nevermind how.
Merely assuming an oracle for the halting function is only one of many ways to build something that does things turning machines can't do.
For example, allowing infinities in various places where the classical theory of computation assumes finite sets also sometimes increases the computational power of machines. E.g., we normally assume that a turing machine's tape is uninitialized or initialize only a finite subset of the tape. But by initializing a turing machine with a carefully selected infinite tape, you can compute the halting function. Some other "now make the finite thing infinite and then code up the halting function" constructions can be found in this paper.
If you fix one of these various constructions, you can start to do all the classical CS theory stuff in the context of a slightly different machine. It's interesting to see results transfer, which break down, and what surprising new/nice results show up here but not in classical cs theory.
It's hard to say how useful any of this is because all of these constructions basically assume we already have at hand something that we have no idea how to construct in reality. I.e., the whole paper begins with "assume false" as far as us pragmatic engineering folk are concerned. But that's perhaps basically the same thing Euclidean geometers said during the emergence of non-Euclidean geometry, so perhaps this work will end up being as revolutionary as turing machines themselves and we just can't see exactly how yet.
There's a famous problem in CS called the halting problem. The halting problem asks for a program that tells you whether an arbitrary program (turning machine) ever halts (a.k.a. stops executing). A function that could compute a solution to the halting problem is called a halting function.
Turning machines can't compute a solution to the halting problem.
Therefore, if you add an oracle for the halting problem to an otherwise normal turing machine, then the resulting model of computation is stronger than turing machines alone. And oracle is basically a magical box that answers your questions in O(1) time, nevermind how.
Merely assuming an oracle for the halting function is only one of many ways to build something that does things turning machines can't do.
For example, allowing infinities in various places where the classical theory of computation assumes finite sets also sometimes increases the computational power of machines. E.g., we normally assume that a turing machine's tape is uninitialized or initialize only a finite subset of the tape. But by initializing a turing machine with a carefully selected infinite tape, you can compute the halting function. Some other "now make the finite thing infinite and then code up the halting function" constructions can be found in this paper.
If you fix one of these various constructions, you can start to do all the classical CS theory stuff in the context of a slightly different machine. It's interesting to see results transfer, which break down, and what surprising new/nice results show up here but not in classical cs theory.
It's hard to say how useful any of this is because all of these constructions basically assume we already have at hand something that we have no idea how to construct in reality. I.e., the whole paper begins with "assume false" as far as us pragmatic engineering folk are concerned. But that's perhaps basically the same thing Euclidean geometers said during the emergence of non-Euclidean geometry, so perhaps this work will end up being as revolutionary as turing machines themselves and we just can't see exactly how yet.