Stephen Wolfram

And so that means that at least at the level of that kind of computation and those kinds of pieces of hardware, there isn't a robust notion of computation.

There's the adding machine kind of computation, there's the multiplying machine notion of computation, and they're disjoint.

So what happened in around 1900, people started imagining, particularly in the context of mathematical logic, could you have something which would represent any reasonable function, right?

And they came up with things, this idea of primitive recursion was one of the early ideas, and it didn't work.

There were reasonable functions that people could come up with that were not represented using the primitives of primitive recursion.

Okay, so then along comes 1931 and Gödel's theorem and so on.

And as in looking back, one can see that as part of the process of establishing Gödel's theorem, Gödel basically showed how you could compile arithmetic, how you could basically compile logical statements like this statement is unprovable into arithmetic.

So what he essentially did was to show that arithmetic

can be a computer in a sense that's capable of representing all kinds of other things.

And then Turing came along in 1936, came up with Turing machines.

Meanwhile, Alonzo Church had come up with lambda calculus.

And the surprising thing that was established very quickly is the Turing machine idea about what computation might be is exactly the same as the lambda calculus idea of what computation might be.

And then there started to be other ideas, you know, register machines, other kinds of representations of computation.

And the big surprise was they all turned out to be equivalent.

So in other words, it might have been the case, like those old adding machines and multiplying machines, that Turing had his idea of computation, Church had his idea of computation, and they were just different.

But it isn't true.

They're actually all equivalent.

So then by, I would say, the 1970s or so, in sort of the computation, computer science, computation theory area, people had sort of said, oh, Turing machines are kind of what computation is.

physicists were still holding out, saying, no, no, no, that's just not how the universe works.

We've got all these differential equations.