5 ms·

Holy cow. It’s amazing to see this on Quanta magazine, because I didn’t think that many people had heard of or were interested in algorithmic information theory

Holy cow. It’s amazing to see this on Quanta magazine, because I didn’t think that many people had heard of or were interested in algorithmic information theory. I’ve been following Hector’s work for a few years and for fun implemented his paper on (brute force) iterating over small Turing machines. This sort of approach is top down — start with the best theory of computation (and in some ways, AGI) and then work backwards to develop computable approximations. Contrast this to the bottom-up approach of neural networks, which is more like “we’ve found these things that work well in specific cases; can we tweak them to do more?” I think ultimately the top down approach is going to be more productive, because there’s a strong theoretical framework already in place that basically sets the upper bound on what you can do. A lot of papers showing progress on computable approximations have been published just within the last year. There was one recently showing that the halting problem is in fact solvable for “almost all” Turing machines, which is a bit surprising; I would have not thought this was the case. Ultimately though, we don’t need to find the absolute shortest Turing machine that produces a given output string — we just need to find a decently short one that performs better than our existing models. Any sort of algorithmic approach is bound to be vastly superior to a purely statistical approach.

paraschopra 8y ago
Can you please link to or point to the recent results in computability theory that you are talking about? Also, is your code for exploring Turing machines public? We could perhaps use it in our project (see my other comment)
- Xcelerate 8y ago
  Looks like the paper is a lot older than I thought it was: https://arxiv.org/abs/math/0504351 https://arxiv.org/abs/math/0504351 My code isn't public at the moment. It's written in Julia and rather messy so I'd have to clean it up a bit, but I wouldn't be opposed to putting it on Github. I really like your project idea btw. It never occurred to me that all that time and energy wasted on proofs of work could be spent approximating the universal distribution. That could be really valuable.
  - paraschopra 8y ago
    Actually I just found out a video on the related idea where halting probability is proposed to be 1 (the argument uses genetic programming techniques): https://www.youtube.com/watch?v=fst40OxKX7o https://www.youtube.com/watch?v=fst40OxKX7o
  - saalweachter 8y ago
    Re: "my code is messy", if it's code you're willing to share, I wouldn't hold messiness -- either in the "it's not properly formatted and all the variables are i, ii, iii, ijk, ..." or in the "I realized the overall structure was wrong and it needs a major refactoring" sense -- to be a barrier to sharing. Most of the problems with sharing messy code are purely in the author's head ("please don't let other people know how terrible my code is") and once you actually bite the bullet and just push the code, it turns out to be like most secrets, really stressful to keep secret and actually not that big of a deal once everyone hears it. And for the real code problems, the broken corner cases and unfinished tests, well, if you put it on Github someone else might fix it for you :-)
amelius 8y ago
> There was one recently showing that the halting problem is in fact solvable for “almost all” Turing machines, which is a bit surprising Is this in the same sense as "almost all numbers are not natural numbers", and if yes, then what good does this bring?
- Xcelerate 8y ago
  Yes, unfortunately. And not much other than I suppose it just seems unintuitive to me that the halting problem is solvable for "most" programs. The real challenge would be to show that "interesting" programs (i.e. that generate some sort of real world data) are solvable. There have been similar efforts in the field of complexity theory that aim to show certain NP-hard problems are tractable in the case of real world data (as opposed to a pathologically selected worst-case problem).
jibal 8y ago
Why is that surprising? The proof that the HP is unsolvable is based on showing that, if there were a solution, it would fail on one specific input.
- kevinventullo 8y ago
  Yeah, I would imagine almost all Turing machines have trivial behavior in some way. To make a more concrete analogy, almost all C++ programs don't compile, and so HP is solvable for them in some degenerate sense.

paraschopra 8y ago

Can you please link to or point to the recent results in computability theory that you are talking about? Also, is your code for exploring Turing machines public? We could perhaps use it in our project (see my other comment)

Xcelerate 8y ago
Looks like the paper is a lot older than I thought it was: https://arxiv.org/abs/math/0504351 https://arxiv.org/abs/math/0504351 My code isn't public at the moment. It's written in Julia and rather messy so I'd have to clean it up a bit, but I wouldn't be opposed to putting it on Github. I really like your project idea btw. It never occurred to me that all that time and energy wasted on proofs of work could be spent approximating the universal distribution. That could be really valuable.
- paraschopra 8y ago
  Actually I just found out a video on the related idea where halting probability is proposed to be 1 (the argument uses genetic programming techniques): https://www.youtube.com/watch?v=fst40OxKX7o https://www.youtube.com/watch?v=fst40OxKX7o
- saalweachter 8y ago
  Re: "my code is messy", if it's code you're willing to share, I wouldn't hold messiness -- either in the "it's not properly formatted and all the variables are i, ii, iii, ijk, ..." or in the "I realized the overall structure was wrong and it needs a major refactoring" sense -- to be a barrier to sharing. Most of the problems with sharing messy code are purely in the author's head ("please don't let other people know how terrible my code is") and once you actually bite the bullet and just push the code, it turns out to be like most secrets, really stressful to keep secret and actually not that big of a deal once everyone hears it. And for the real code problems, the broken corner cases and unfinished tests, well, if you put it on Github someone else might fix it for you :-)

amelius 8y ago

> There was one recently showing that the halting problem is in fact solvable for “almost all” Turing machines, which is a bit surprising Is this in the same sense as "almost all numbers are not natural numbers", and if yes, then what good does this bring?

Xcelerate 8y ago
Yes, unfortunately. And not much other than I suppose it just seems unintuitive to me that the halting problem is solvable for "most" programs. The real challenge would be to show that "interesting" programs (i.e. that generate some sort of real world data) are solvable. There have been similar efforts in the field of complexity theory that aim to show certain NP-hard problems are tractable in the case of real world data (as opposed to a pathologically selected worst-case problem).

jibal 8y ago

Why is that surprising? The proof that the HP is unsolvable is based on showing that, if there were a solution, it would fail on one specific input.

kevinventullo 8y ago
Yeah, I would imagine almost all Turing machines have trivial behavior in some way. To make a more concrete analogy, almost all C++ programs don't compile, and so HP is solvable for them in some degenerate sense.