5 ms·

If you somehow know BB numbers, you know the size of finite memory, which is sufficient to run corresponding busy-beaver. Limiting mathematics to what is physic

If you somehow know BB numbers, you know the size of finite memory, which is sufficient to run corresponding busy-beaver. Limiting mathematics to what is physically possible is not useful. We don't know what is ultimately physically possible.

adrianN 6y ago
We have some upper bounds on what is physically possible: https://arxiv.org/abs/quant-ph/9908043 https://arxiv.org/abs/quant-ph/9908043
- jonathanstrange 6y ago
  Wait a minute, does this paper include various hypercomputers or is it only about conventional computation? Although I personally believe hypercomputers are not physically possible, I'm not aware of any general proof that they are physically impossible. I've seen papers that suggest physical models for hypercomputers. Notice that there is a hierarchy of hypercomputers of varying powers and some of them can solve the Halting Problem.
  - adrianN 6y ago
    The paper includes quantum computers, it does not include computers that exploit CTCs or similar things whose existence we can only speculate upon. Note however that CTCs don't give you hypercomputation. Do you have a link discussing physical models for hypercomputers?
    - jonathanstrange 6y ago
      Most papers criticize the idea and describe physical limits. I don't remember which one on the physical possibility of hypercomputation I read (a long time ago), but there are some papers such as the following: https://oronshagrir.huji.ac.il/sites/default/files/oronshagrir/files/physical_hypercomputation_and_the_church-turing_thesis.pdf https://oronshagrir.huji.ac.il/sites/default/files/oronshagr... https://link.springer.com/article/10.1007/s11047-009-9114-3 https://link.springer.com/article/10.1007/s11047-009-9114-3 https://sci-hub.do/10.1142/S0129626412400105 https://sci-hub.do/10.1142/S0129626412400105 An overview is in A. Syropoulos: Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer 2008, chapters 8-9. Gotta love the subsection headline in the third paper mentioned above: "A CTC Based Relativistic Hypercomputer That Actually Works Without Problems." ;-)

adrianN 6y ago

We have some upper bounds on what is physically possible: https://arxiv.org/abs/quant-ph/9908043 https://arxiv.org/abs/quant-ph/9908043

jonathanstrange 6y ago
Wait a minute, does this paper include various hypercomputers or is it only about conventional computation? Although I personally believe hypercomputers are not physically possible, I'm not aware of any general proof that they are physically impossible. I've seen papers that suggest physical models for hypercomputers. Notice that there is a hierarchy of hypercomputers of varying powers and some of them can solve the Halting Problem.
- adrianN 6y ago
  The paper includes quantum computers, it does not include computers that exploit CTCs or similar things whose existence we can only speculate upon. Note however that CTCs don't give you hypercomputation. Do you have a link discussing physical models for hypercomputers?
  - jonathanstrange 6y ago
    Most papers criticize the idea and describe physical limits. I don't remember which one on the physical possibility of hypercomputation I read (a long time ago), but there are some papers such as the following: https://oronshagrir.huji.ac.il/sites/default/files/oronshagrir/files/physical_hypercomputation_and_the_church-turing_thesis.pdf https://oronshagrir.huji.ac.il/sites/default/files/oronshagr... https://link.springer.com/article/10.1007/s11047-009-9114-3 https://link.springer.com/article/10.1007/s11047-009-9114-3 https://sci-hub.do/10.1142/S0129626412400105 https://sci-hub.do/10.1142/S0129626412400105 An overview is in A. Syropoulos: Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer 2008, chapters 8-9. Gotta love the subsection headline in the third paper mentioned above: "A CTC Based Relativistic Hypercomputer That Actually Works Without Problems." ;-)