Post #3942338

2026-07-18 10:14 UTC

I have corrected the Grover’s algorithm code at http://crudfactory.com/PHYSICS.html It now takes a predicate closure to tell it what to search for. Before you actually had to give it the answer to get the answer! This was what the inference engine interpreted an ‘Oracle’ to be. Oracles are practically impossible to understand, to me. They come from Turing theory, don’t they? Well, I’m a functional programmer (though I do often write Ada). #computing #quantumComputing #physics #science #mathematics

Replies (1)

@FishFace@ioc.exchange 2026-07-19 21:14

@chemoelectric@masto.ai they come from computability theory, which is also where Turing machines pop up. You will know that not all questions you can ask of a computer can be answered with a computer program: some questions like "will this program halt after finitely many steps" are uncomputable. This is Turing's theorem on the Halting Problem. But imagine if you had a magic box that you put computer code into and told you whether they would halt or not, then *with that* you could write a program which solves the Halting Problem, just by feeding the code into the box and seeing what it said. The box is an "oracle". The reason this is interesting is because you now have a new question: what are the questions which are computable if you have access to the oracle? Clearly the Halting Problem is then solvable, but other questions are, too. So, are all questions solvable? Nope! You can run the same argument as Turing's original in this new system to get another unsolvable problem in that system. What if you keep adding oracles and finding unsolvable problems? Will you eventually eliminate every unsolvable problem? The answer is "no", not for any countable iteration of this process. Doing this once is called the Turing Jump, and it's in operator in the system of Turing Degrees. This is a very small part of a big area!

Open ##3942337