5 ms·

I'm kind of rusty on algorithmic information theory (I'm an artist, heh)! Is there such a thing as (formalized) upper limit of what we could do as far as comput

I'm kind of rusty on algorithmic information theory (I'm an artist, heh)! Is there such a thing as (formalized) upper limit of what we could do as far as computing combinations go? I know of Kolmogorov complexity (vaguely), but what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success? I plan on developing a story around that and make a movie out of it - so any help would be appreciated (you guys can contact me via email if you want).

itry 14y ago
"what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success?" According to current theory of physics, every computation needs at least a certain amount of energy. So if you want to do many computations today, you will have to use a certain amount of energy today. Now lets say, you have a machine that turns any matter into energy without any loss. You put in m mass and you get out e=mc^2 energy. Problem is: You cannot get more matter into that machine today then is around you in a radius of 24 light hours. So that would be a hard limit. But quantum computers have proven to break that limit. One theory is that using a quantum computer means using computers in an unlimited number of parallel universes. So there is no limit to the number of calculations you can do. (See David Deutsch and his theories about parallel universes) I think there are theories about the limits of what a quantum computer can calculate. But I dont know them. Would be interesting to read about it if there is something published. Then again, what might look like a "hard limit" today will probably not do so tomorrow. Some time ago the "lower limit on energy per calculation" sounded like a hard limit. Then quantum computers came along and blasted through it.
- Keyframe 14y ago
  Thanks for info. Also, I found somewhat of an answer for limits of computations I was looking for: http://en.m.wikipedia.org/wiki/Bremermann%27s_limit http://en.m.wikipedia.org/wiki/Bremermann%27s_limit rather fascinating!
- AnIrishDuck 14y ago
  > According to current theory of physics, every computation needs at least a certain amount of energy. This is not, strictly speaking, true. You are talking, I believe, about Lanadauer's principle [1]. This states that it is the destruction of entropy that costs energy. There are computational methods that can theoretically avoid these energy losses [2]. In fact, Lanadaer theorized about reversible computing in his original paper [3]. Bremmerman's limit, mentioned below, is more applicable. 1. http://en.wikipedia.org/wiki/Landauer%27s_principle http://en.wikipedia.org/wiki/Landauer%27s_principle 2. http://en.wikipedia.org/wiki/Reversible_computing http://en.wikipedia.org/wiki/Reversible_computing 3. http://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf http://www.cc.gatech.edu/computing/nano/documents/Bennett%20...
marshray 14y ago
I read a reference someone posted somewhere once (sorry to not be more specific) that sounded pretty convincing. Apparently it takes a minimum amount of energy to flip one bit in a conventional (non quantum) computer. In order to brute force a 128 bit key, you'd need some sort of 128 bit register. Multiply the amount of energy needed per bit flip and the result implies there are never likley to be enough power plants on Earth to iterate through all the combinations (let alone perform the computations required to test the candidate key). Hope this helps, perhaps this is enough for you to find the original reference. Edit: perhaps it was http://en.wikipedia.org/wiki/Landauer%27s_principle http://en.wikipedia.org/wiki/Landauer%27s_principle as mentioned below.
- Keyframe 14y ago
  I'm mapping through all the concepts I need and try to grasp, at least, basic knowledge about it. It helps I'm math literate (to an extent), but I still have a long way to go before I have a believable premise (+ a magic/unknown factor to make an interesting story) before I contact an expert in information theory to make it even more believable. I suspect this will be the king of "nerd" movies, but I don't care - it's something I would watch, that is all that matters for that project.
  - marshray 14y ago
    I can't wait to see it!

itry 14y ago

"what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success?" According to current theory of physics, every computation needs at least a certain amount of energy. So if you want to do many computations today, you will have to use a certain amount of energy today. Now lets say, you have a machine that turns any matter into energy without any loss. You put in m mass and you get out e=mc^2 energy. Problem is: You cannot get more matter into that machine today then is around you in a radius of 24 light hours. So that would be a hard limit. But quantum computers have proven to break that limit. One theory is that using a quantum computer means using computers in an unlimited number of parallel universes. So there is no limit to the number of calculations you can do. (See David Deutsch and his theories about parallel universes) I think there are theories about the limits of what a quantum computer can calculate. But I dont know them. Would be interesting to read about it if there is something published. Then again, what might look like a "hard limit" today will probably not do so tomorrow. Some time ago the "lower limit on energy per calculation" sounded like a hard limit. Then quantum computers came along and blasted through it.

Keyframe 14y ago
Thanks for info. Also, I found somewhat of an answer for limits of computations I was looking for: http://en.m.wikipedia.org/wiki/Bremermann%27s_limit http://en.m.wikipedia.org/wiki/Bremermann%27s_limit rather fascinating!
AnIrishDuck 14y ago
> According to current theory of physics, every computation needs at least a certain amount of energy. This is not, strictly speaking, true. You are talking, I believe, about Lanadauer's principle [1]. This states that it is the destruction of entropy that costs energy. There are computational methods that can theoretically avoid these energy losses [2]. In fact, Lanadaer theorized about reversible computing in his original paper [3]. Bremmerman's limit, mentioned below, is more applicable. 1. http://en.wikipedia.org/wiki/Landauer%27s_principle http://en.wikipedia.org/wiki/Landauer%27s_principle 2. http://en.wikipedia.org/wiki/Reversible_computing http://en.wikipedia.org/wiki/Reversible_computing 3. http://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf http://www.cc.gatech.edu/computing/nano/documents/Bennett%20...

marshray 14y ago

I read a reference someone posted somewhere once (sorry to not be more specific) that sounded pretty convincing. Apparently it takes a minimum amount of energy to flip one bit in a conventional (non quantum) computer. In order to brute force a 128 bit key, you'd need some sort of 128 bit register. Multiply the amount of energy needed per bit flip and the result implies there are never likley to be enough power plants on Earth to iterate through all the combinations (let alone perform the computations required to test the candidate key). Hope this helps, perhaps this is enough for you to find the original reference. Edit: perhaps it was http://en.wikipedia.org/wiki/Landauer%27s_principle http://en.wikipedia.org/wiki/Landauer%27s_principle as mentioned below.

Keyframe 14y ago
I'm mapping through all the concepts I need and try to grasp, at least, basic knowledge about it. It helps I'm math literate (to an extent), but I still have a long way to go before I have a believable premise (+ a magic/unknown factor to make an interesting story) before I contact an expert in information theory to make it even more believable. I suspect this will be the king of "nerd" movies, but I don't care - it's something I would watch, that is all that matters for that project.
- marshray 14y ago
  I can't wait to see it!