3 ms·
It's not an oracle. 'equivalent to the halting problem' just means 'your system is a turing machine'. >Even if someone attempted to build one of the machines d
by Legend2440 2y ago
It's not an oracle. 'equivalent to the halting problem' just means 'your system is a turing machine'.
>Even if someone attempted to build one of the machines depicted in these blueprints, however, researchers point out that undecidability is a feature of physical theories and cannot literally exist in real experiments. Only idealized systems that involve infinity — an infinitely long tape, an infinitely extensive grid of particles, an infinitely divisible space for placing pinballs and rubber ducks — can be truly undecidable.
- andrewflnr 2y agoIt's a property that can be measured in finite (constant?) time, that's determined by a halting-complete problem. Unless I drastically misunderstood, and except for the whole finite-size thing.
- rstuart4133 2y agoI didn't understand the think completely (I suspect you would have to read the page) but they do mention a Turing machine with an infinite tape several times, then they say they used the quantum states of a finite sized system to emulate that tape. That makes sense. You can always in principle determine if a finite system halts (although resource constraints mean you may not be able to do so in practice). So their system must be able to contain an infinite amount of information despite being finite in size. But that does mean they are assuming an infinity lurks within every qubit. I didn't realise we understood quantum so well we can confidently make that assumption.