For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
sgt101
Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection).
Our world appeared computable, but it isn't, even if P=NP.
show comments
summarybot
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
jojogeo
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection).
Our world appeared computable, but it isn't, even if P=NP.
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?