Knuth does computer science, which is kind of programming for mathematicians, not martians, (while both groups might share some characteristics:-)
However I still wait to see someone who had time to work through all three existing volumes,
and completed the tackable exercises.
So as a course for computer science, I think
this series is a failure, as it covers simply too much. Perhaps one should regard it more as a
encyclopedia.
This is no fallback to natve widgets.
It just allows for the the widgets to get
rendered differently!
So the Swing controls look more like
Windows controls using the Windows look, but
they are still realized by Swing routines.
IMHO Windows look is mimicked, but not Windows
feel.
Hold on a second. The architecture Swing uses *is* good. The performance, pre-v1.4, did suck, but that was because Swing was pure-Java. In v1.4, Swing finally utilizes native code to handle optimizations for elements like scrolling. Consequently, jdk1.4 feels much faster, subjectively matching the speed of native GUIs.
The typical modern Java client application
runs well only on Win32. Well meaning at
acceptable speed and stability.
Modern meaning fast Swing, Java 3d, perhaps
WebStart etc.
Linux and Solaris are already less suited.
Users of unsupported plattforms, like the
BSDs, are left alone.
This is quite a shift from portable to
running well on the top plattforms only.
My point is just that you should really give v1.4 a chance. It's quite nice, despite changing a few of the APIs such that many v1.3 programs must be ported (very few changed, but just enough that it's not a simple copy-and-run for programs like Forte).
The Swing scrolling optimization in 1.4 for Win32 is making use of DirectX, featuring a new Swing callback, in case a surface invalidated.
If somebody told me such a few years ago about Java,
I would have laughed at him.
I still say, why bother? java's here, since yesteryear, now, and has already seen huge adoption by the mobile computing device market in europe and asia (US lags in this market).
Microsoft simply want to leverage their desktop penetration into server and mobile device space. They've dissed java for years, trying, and to some extent succeeding, in slowing adoption of java. Now that they've got their own implementation of essentially the same ideas, they suddenly want us to think it's wonderful.
Windriver aquired BSDi, interested in getting
BSD technology for the embedded market.
So with Microsoft's move, it might be possible
to get.NET running on such devices too.
On the other hand, I have not seen anything
that prevents a port of that.NET implementation
to Linux.
I guess that embedded people will get a large choice of what OS to use (proprietary, Linux or
BSD based) and what crossplatform runtime (Java
or.NET based).
The outcome of a travelling salesman problem is not a state change, unless you think you can solve the problem by flipping a bit.
These problems can be mapped onto bits and these
can be mapped into the qbits of a quantumn computer.
If we had to tour 2^n cities, the data set would
consist of tuples (city1,.., city2^n).
We could map that onto 2^n x 2^n = 2^2n bits.
So we would need a 2^2n quantum bits in a quantumn computer, that represent the 2^(2^2n)
possible outcomes.
This boils down to question if it will be possible
to get such a large number of qbits in superposition. I believe nobody knows if this is
physically or technically possible.
We also don't know if there is some experimental
setup, whose measurement would collapse
that superposition into the optimal TSP soulution.
Perhaps a whole series of more fundamental
computational steps/measurements needs to be
done by a quantumn computer.
Like I wrote above, I don't know what kind of basic quantumn computing operations are possible
to built, but I believe that it could be more complex ones that simple increments. I am sure a look over the fence into the domain of analog computing would give some useful hints of what
might be possible.
Even if you use the physical analogue of creating lengths of strings tied together at the various city nodes and pull the "cities" in question until the strings are tight and selecting the tight path, every atom moving in the process is a state change
It will possibly not such a simple mechanical setup but some much more crazy arrangement of
basic quantumn computing components, that implement
abstract operations. Perhaps it is not a single
state change but it might turn out to need qualitativley much less than an algorithm on a classical computer.
And even if you prove that P=NP, you still need an algorithm that traverses the data, examines it, compares different links, etc, and every step in the algorithm is AT LEAST a state change
The reasoning from classical complexity theory shows that the work of digesting the input data
is part of the overall work, an algorithm performs. But it is also true, that the models
assume that one symbol of input data is digested
at a time. Perhaps the inherent paralellism of
a quantumn computer can save effort here to,
by having some read-all-input-at once feature.
I simply don't know.
Hm.. I should really try to get an expert
to judge this discussion.
Your input data corresponds to the initial states of the system
Actually, the preparation of the initial states is already part of the quantumm computational
solution procedure.
For example the idea behind a quantum computer doing a massive parallel database query would be to have all possible search results feature in the superposition of the inital states of the system.
The query would be the measurement that picks
that state as final state, that represents
the match.
You misunderstand what it means for a problem to be complex. NO NP-HARD PROBLEM CAN BE SOLVED BY A DETERMINISTIC MACHINE IN POLYNOMIAL TIME. none, nada.
You Sir, misunderstand what this kind of theoretical computer science is about.
It is using a mathematical theory: using mathematical objects like sets and mappings, a simple mathematical model is formulated. Then one tries to analyze the implications of this model
by application of the laws of mathematical logic.
The mathematical model you are talking about is the register machine or Turing machine (or a model of equivalent computational strength).
What you cited in upper case is a logical consequence, a theorem or lemma,
thus a truth for just this model.
What makes this computer science and not plain mathematics is, that we believe that these simple models are adequate representations of what we think computers and computations are.
One of the fundamental assumptions of these models, and that is why I call them classical computational models, is that they are based on a thinking that corresponds to the
common sense thinking of classical physics.
Like you said, these models assume that only one fundamental operation can be performed in one
time step (clock cylcle, whatever unit of time).
But, as Feynman never stopped to preach, nature is not classical! It is much more strange.
Experiments verify that nature has some weirdnesses only accurately described by quantumn mechanics or theory of relativity so far.
These are results that are not compatible with
commons sense, but are still compatible with
the mathematical models of theoretical physics,
thus compatible with mathematical logic.
And that is where quantumn computing comes into place. What happens if one makes use of this strange effects, like two photons that seem to interact with no time delay, although they are far apart, or the phenomenom what is colled as
collapse of the wave function in quantumn
mechanics, to build a faster computer?
Somehow quantum computers are supposed to make this nondeterministic which means that given a single state I can be in multiple states after the next step, and somehow the right one is picked out at the end.
You surely heard of Schroedinger's cat.
It is a truth from quantumn mechanics, that
systems can be in an entangled/mixed state
and that only the act of measurement/looking will
put it into an decisive output state.
The act of measurement itself is one of the conceptual weaknesses of quantumn mechanics.
Most physicists just take for granted that
it happens and know how to deal with it in calculations and experimental setup.
The theory behind it is hardly distinguishable from philosophy. (As far as I understood, it is
the problematic of observed system and observer
who really can't be seperated into two entities,
with two wavefunctions, but are connected, and thus would be described only be a common wavefunction. This way it is hard to get results. We would ultimately have to analyze the wavefunction of the whole universe to get results.
Thanks god, this not necessary most of the time, the conceptual separation of the universe into seperate physical subsystems is often useful)
As our minds were evolved in a environment that is mostly goverend by classical physics, we have really trouble to grasp such strange truths.
We know the formulas and are able to set up experiments and get results, but this no intuitive
understanding.
To quote Feynman again, he was sure that nobody
understood quantumn mechanics.
The radical idea behind quantumn computing is to take advantage of these strange effects. (strange to us classical minds, perhaps not strange to some hypothetical life form evolved in an environment where quantumn mechanics would be dominant in every day life)
I just don't buy into taking a deterministic model of computation (which the article seems to be using) and expecting it to crank out the general travelling salesman problem in any reasonable time.
It is hard to common-sense recognize that while the quantumn physical processes are governd by probabilities, the laws that govern these probabilities are exact. For example a given
process might have a random outcome, but still
I can deduce from the laws that it must have a probability less than 1/3, and can make use of that given bound in the construction of my machine. You see, randomness does not mean, that
there is no prediction possibly, also the kind
of predictive strength is much less than in classical physics, it is still much beter than using a crystal ball.
Due to their propabilistic natures, quantum computers were thought to be very instable
and not able to yield deterministic results.
The first crucial idea of quantumn computing was
Feynman's (?) idea of recognizing classical computation/complexity theory as based on assumptions of classical physics and thus exploiting the not before used quantumn mechanical behaviour computationally, as
described above.
The second crucial idea was Peter Shor's idea of
using error correction strategies in the context
of quantumn computing.
As I understood, this was the theoretical break through. That idea provides the needed stability.
Shor by the way, was also the guy who proposed
the prime factorization algorithm that was qualitativly better than anything classical computational/complexity theory said.
mvw, what part of "This is how fast state changes can happen" don't you understand?
You imply that I challenged this physical upper limit on state change rate in this discussion, but I did not.
My point is different. It goes down to the question about the relationship between rate of state changes on one hand, and the ability to
perform a fast computation on the other hand.
The naive view is similiar to the view many
cpu buyers have in regard of clocking speed.
It goes along the line "The more MHz, the faster the CPU".
As we know, this is not
a valid measure to compare for example a Pentium IV and a PPC CPU. They are not comparable by
clocking speed alone. Eg the one cpu might perform a floating point multiplication much faster than the other cpu in terms of clock cycles.
The classical theories of computation solve this
problem, by mapping programs onto a very simple
model of a computer, the Turing machine or register machine, or real RAM and then doing comparisions. The operations in these models
are precisely defined, like incrementing a register, or decrementing a register, or testing if it is zero.
As we know there, a computation needs a certain number of basic operations as well as a certain
amount of memory. Classical complexity theory tells us, how exactly memory and number of needed operations are related for these easy computation
models. In fact both are subject to the "size" of the input data as well. Like I said, this only well understood for these deliberatly simple choosen computation models (Turing machines etc).
In this discussion, we were talking about limitations of computing. It makes sense to think about the most powerful computing architecture envisioned so far. And that is the model of quantumn computer at present.
In this setup your computer is a quantumn mechanical system. Your input data corresponds to the initial states of the system, your computation is a measurement of the system, this meaning a physical process that kicks the system from its inital state into its final state,
the final state encoding your result data.
The trick with quantumn computers is that
one arranges that measurement to reduce a large
number of possible solutions/states into one
final state. This is decribed sometimes as doing all computations at once.
You will immediatley notice, that computation in this setup is achieved by exactly one state change,
the measurement that kicks your system into
final state.
Now lets translate this abstract mumbo jumbo back into real things.
The first quantumn systems explored were some couple of nucleii in a big magnet, a NMR mesurement device. Initial state corresponds
to some inital states of these nucleii, typically their rotational and spin degrees of freedom.
Measurement means bombing these nucleii with some electromagnetic radiation and looking for the
states of the nucleii after that.
What must be achieved by the experment is, that
we must be able to map the input data of a problem onto the initial states of these nucleii.
The output states must also correspond to a solution of the problem under consideration. Further the measurement process must correspond to the solution procedure of the problem.
As we have ttl logic gates for simple operations
like AND OR NOT, researchers have to think of building quantumn logic gates. Thus systems that can handle input data with their initial states, where act of measurement corresponds to some useful operation on the input data, and the output states can be translated back into a nice
result on the input data.
Question: What kind of operation can be encoded by such an experiment?
Actually I don't know. I believe however that it might be a very complex one. Take for example
a chain. It just hangs down and by this finds an optimal solution to a variational problem.
Or fire some photons from air into water,
the travel in way, that corresponds again to the
solution of a hairy differential equation.
Or a chemical reaction with many molecules
can solve some crazy combinatorical problem
in a couple of microseconds.
The topic touched here, is the topic of representation. Everyone with a decent level of math knows, that there are different representations of the same problem, the one harder to solve, the other easier.
In fact this on of the basic problem solving strategies in applied mathematics:
find a representation where a problem is easy
transform problem into that context
solve problem in the easy representation
transform problem (and solution) back
Examples are diagonalization of matrices or finding of the inverse of an integral operator (eg Green's functions in partial differential equations) by Fourier transformation, algebraic invertation, and Fourier back transformation.
So in this regard I want to argue that we can choose different physical setups that might
enable us to do a more or less complex computation
in one state change.
So it is not only about quantity (number of states changes) but also about quality (what computation is performerd with this change).
No, the limitations that technology can overcome are engineering limitations. The limitations talked about in the article are basic fundamental physics limitations that don't depend on any particular form of technology.
Considering the physical theory (here: non relativistic quantumn mechanics, which is still an approximation of nature) used to derive
the limitations is sufficient.
The only reason for quantum mechanics in this article is the fact that quantum mechanics gives a lower bound for miniaturisation (i.e. you can only keep making computer parts smaller until you get problems with the Heisenberg Unertainty Principle)
Actually short times allow for high energy fluctuations (dt * dE >= hbar), this is the very basic reasoning for the existance of short
lived (so called virtual) particles in quantumn field theory, with its complications on the number of particle being not constant in physical process and the fact that one can not observe bare bone particles.
This could mean that fast
processes have to deal with disturbance from
such energy fluctuations, providing physical
limits as well for fast computing.
Your example is one, that can't take advantage of parallelism.
I would rather give an divide and conquer type algorithm (like sorting) as example for recursion and parallelism.
Who says that a complex problem needs a high number of state changes?
Each state change could be the result of a
very high level operation, not something primitive like adding two numbers,
but perhaps something like the outcome of the
traveling salesman problem. Think of some
clever physical setup here.
It will be due to the cleverness of the computer builders, to make most use out of the limitations.
Now before you say "BS", think about it. In physics, if you know the initial state (starting position, velocity, acceleration) of an object in an isolated system, you can easily compute where it was at any given time earlier. This uses the same concept. For example, If you add 43 to a register, you can subtract 43 from that register and get your energy back.
There are parallel machines out there. As much as I heard, the attempt to generate parallelizing compilers, thus compilers that take a conventional program, analyze its structure and try to generate code that takes advantage of the parallel hardware,
has not been very successful.
And of course it depends totally on the problem,
if parallelism can be exploited.
It's all a matter of any physical system having a bounded energy having a corresponding bounded rate of state change.
But like writing fast or dog slow programs with a given programming language, there might be very different approaches (regarding computational power) to use the physics for building fast
computers.
Thus there is a physical limit, as well as a logical limit (theories of computation and complexity) to consider.
Note that the given speed limit is on state change rate. Those states could represent much more complex operations than simple arithmetic.
All in all the article is nice, but I enjoyed the one on Hans Moravec's page more, where Feynman pondered about the ultimate library.
Regards,
Marc
You are pulling me leg, aren't you?:)
The Japanese are probably more picky considering cleanliness than the Swiss and you tell me they show something like this between children TV?
Well they certainly don't mind showing extreme violence even for childs, but I doubt your claim.
Or a company sponsoring rape?
Very unlikely.
Not bad, troll-baku.
plus another link to an article of an expert system builder who wrote how a real HAL ought to work.
I must admit that I get very tired of the Slashdot submission process. I submitted a long list of entries this year, and only two or so were posted
to the Slashdot frontpage.
Not that I expect that my taste is 100% compatible with the taste of the editors, but as
they never give the slightest feedback, why an article was rejected, this reduces my motivation to submit IMHO interesting bits to Slashdot
more and more.
The only alternative I see to Slashdot, next
to establishing another service, is Kuro5hin.
Alas the fellow geek crowd is centered around Slashdot. The Kuro5hin crowd, as it is these
days, seems less technical/hacker to me. Less
engineers, more socio/artist type of folks there.
The Kuro5hin submission process is much better,
but it tends to double discussions.
First matters are discussed in the pre-run
mode and then stuff is moved forward to the main
page, where discussion takes place a second time.
This takes too much drive out of discussions, I believe.
So come on, Slashdot editors, if you reject a submission, please send an email with a word or
two of explanation. It is very hard to judge from rejection alone, what is not OK with submission entries.
one easy way to make a pretty secure connection would be to make little enigma-esque scrambler wheels on the keyboard and base station. since the number of intercepted characters is probably low, your key length doesn't have to be outrageous to provide some security.
There is really no big difference between sniffing a telnet session with bpf and sniffing
an optical or radio connected mouse or keyboard.
One solution for the telnet case was the use of encrypted channels, via the secure socket layer (SSL) and a changed protocol/tool (ssh).
It is obvious that a similiar method has to
be used for the mouse/keyboard case.
So install sshd on your peripherials and be happy:-)
Was he in the famous Microsoft team photo from 1978 - the scary one where almost everyone has terrifying arrangements of facial except for the young CEO - and could he please identify himself? As it happens, he wasn't there, but he does shed light on its origins:-
"That was taken after my second summer, working on the second BASIC for Microsoft. The story there is that Bob Greenberg (center right) had won a prize from a photo lab, which was a free photo shoot." So the first corporate publicity shot came about completely by chance.
The stories of these people can be found
here for example.
I think it is right, that we should fight with producing better software.
What I fear however is lack of support from the hardware vendors. Certain hardware development like nvidia's 3d chips is driven in direct cooperation with Microsoft.
A similiar example is DVD decoding software, Apple's Quicktime, Real's line of products,
Sun's Java software.
The Linux community is able to use most of these, by provided binary releases. Platforms, that are not able to make use of these binaries are left out.
Slashdot Mirror
However I still wait to see someone who had time to work through all three existing volumes, and completed the tackable exercises.
So as a course for computer science, I think this series is a failure, as it covers simply too much. Perhaps one should regard it more as a encyclopedia.
This is no fallback to natve widgets. It just allows for the the widgets to get rendered differently!
So the Swing controls look more like Windows controls using the Windows look, but they are still realized by Swing routines. IMHO Windows look is mimicked, but not Windows feel.
The typical modern Java client application runs well only on Win32. Well meaning at acceptable speed and stability. Modern meaning fast Swing, Java 3d, perhaps WebStart etc.
Linux and Solaris are already less suited.
Users of unsupported plattforms, like the BSDs, are left alone.
This is quite a shift from portable to running well on the top plattforms only.
My point is just that you should really give v1.4 a chance. It's quite nice, despite changing a few of the APIs such that many v1.3 programs must be ported (very few changed, but just enough that it's not a simple copy-and-run for programs like Forte).
The Swing scrolling optimization in 1.4 for Win32 is making use of DirectX, featuring a new Swing callback, in case a surface invalidated. If somebody told me such a few years ago about Java, I would have laughed at him.
Microsoft simply want to leverage their desktop penetration into server and mobile device space. They've dissed java for years, trying, and to some extent succeeding, in slowing adoption of java. Now that they've got their own implementation of essentially the same ideas, they suddenly want us to think it's wonderful.
Windriver aquired BSDi, interested in getting BSD technology for the embedded market. So with Microsoft's move, it might be possible to get .NET running on such devices too.
On the other hand, I have not seen anything that prevents a port of that .NET implementation
to Linux.
I guess that embedded people will get a large choice of what OS to use (proprietary, Linux or BSD based) and what crossplatform runtime (Java or .NET based).
These problems can be mapped onto bits and these can be mapped into the qbits of a quantumn computer.
If we had to tour 2^n cities, the data set would consist of tuples (city1, .., city2^n).
We could map that onto 2^n x 2^n = 2^2n bits.
So we would need a 2^2n quantum bits in a quantumn computer, that represent the 2^(2^2n) possible outcomes.
This boils down to question if it will be possible to get such a large number of qbits in superposition. I believe nobody knows if this is physically or technically possible.
We also don't know if there is some experimental setup, whose measurement would collapse that superposition into the optimal TSP soulution.
Perhaps a whole series of more fundamental computational steps/measurements needs to be done by a quantumn computer.
Like I wrote above, I don't know what kind of basic quantumn computing operations are possible to built, but I believe that it could be more complex ones that simple increments. I am sure a look over the fence into the domain of analog computing would give some useful hints of what might be possible.
Even if you use the physical analogue of creating lengths of strings tied together at the various city nodes and pull the "cities" in question until the strings are tight and selecting the tight path, every atom moving in the process is a state change
It will possibly not such a simple mechanical setup but some much more crazy arrangement of basic quantumn computing components, that implement abstract operations. Perhaps it is not a single state change but it might turn out to need qualitativley much less than an algorithm on a classical computer.
And even if you prove that P=NP, you still need an algorithm that traverses the data, examines it, compares different links, etc, and every step in the algorithm is AT LEAST a state change
The reasoning from classical complexity theory shows that the work of digesting the input data is part of the overall work, an algorithm performs. But it is also true, that the models assume that one symbol of input data is digested at a time. Perhaps the inherent paralellism of a quantumn computer can save effort here to, by having some read-all-input-at once feature. I simply don't know.
Hm.. I should really try to get an expert to judge this discussion.
Actually, the preparation of the initial states is already part of the quantumm computational solution procedure.
For example the idea behind a quantum computer doing a massive parallel database query would be to have all possible search results feature in the superposition of the inital states of the system.
The query would be the measurement that picks that state as final state, that represents the match.
You Sir, misunderstand what this kind of theoretical computer science is about.
It is using a mathematical theory: using mathematical objects like sets and mappings, a simple mathematical model is formulated. Then one tries to analyze the implications of this model by application of the laws of mathematical logic.
The mathematical model you are talking about is the register machine or Turing machine (or a model of equivalent computational strength). What you cited in upper case is a logical consequence, a theorem or lemma, thus a truth for just this model.
What makes this computer science and not plain mathematics is, that we believe that these simple models are adequate representations of what we think computers and computations are.
One of the fundamental assumptions of these models, and that is why I call them classical computational models, is that they are based on a thinking that corresponds to the common sense thinking of classical physics. Like you said, these models assume that only one fundamental operation can be performed in one time step (clock cylcle, whatever unit of time). But, as Feynman never stopped to preach, nature is not classical! It is much more strange. Experiments verify that nature has some weirdnesses only accurately described by quantumn mechanics or theory of relativity so far. These are results that are not compatible with commons sense, but are still compatible with the mathematical models of theoretical physics, thus compatible with mathematical logic. And that is where quantumn computing comes into place. What happens if one makes use of this strange effects, like two photons that seem to interact with no time delay, although they are far apart, or the phenomenom what is colled as collapse of the wave function in quantumn mechanics, to build a faster computer?
Somehow quantum computers are supposed to make this nondeterministic which means that given a single state I can be in multiple states after the next step, and somehow the right one is picked out at the end.
You surely heard of Schroedinger's cat. It is a truth from quantumn mechanics, that systems can be in an entangled/mixed state and that only the act of measurement/looking will put it into an decisive output state. The act of measurement itself is one of the conceptual weaknesses of quantumn mechanics. Most physicists just take for granted that it happens and know how to deal with it in calculations and experimental setup. The theory behind it is hardly distinguishable from philosophy. (As far as I understood, it is the problematic of observed system and observer who really can't be seperated into two entities, with two wavefunctions, but are connected, and thus would be described only be a common wavefunction. This way it is hard to get results. We would ultimately have to analyze the wavefunction of the whole universe to get results. Thanks god, this not necessary most of the time, the conceptual separation of the universe into seperate physical subsystems is often useful)
As our minds were evolved in a environment that is mostly goverend by classical physics, we have really trouble to grasp such strange truths. We know the formulas and are able to set up experiments and get results, but this no intuitive understanding. To quote Feynman again, he was sure that nobody understood quantumn mechanics.
The radical idea behind quantumn computing is to take advantage of these strange effects. (strange to us classical minds, perhaps not strange to some hypothetical life form evolved in an environment where quantumn mechanics would be dominant in every day life)
I just don't buy into taking a deterministic model of computation (which the article seems to be using) and expecting it to crank out the general travelling salesman problem in any reasonable time.
It is hard to common-sense recognize that while the quantumn physical processes are governd by probabilities, the laws that govern these probabilities are exact. For example a given process might have a random outcome, but still I can deduce from the laws that it must have a probability less than 1/3, and can make use of that given bound in the construction of my machine. You see, randomness does not mean, that there is no prediction possibly, also the kind of predictive strength is much less than in classical physics, it is still much beter than using a crystal ball.
Due to their propabilistic natures, quantum computers were thought to be very instable and not able to yield deterministic results.
The first crucial idea of quantumn computing was Feynman's (?) idea of recognizing classical computation/complexity theory as based on assumptions of classical physics and thus exploiting the not before used quantumn mechanical behaviour computationally, as described above.
The second crucial idea was Peter Shor's idea of using error correction strategies in the context of quantumn computing. As I understood, this was the theoretical break through. That idea provides the needed stability.
Shor by the way, was also the guy who proposed the prime factorization algorithm that was qualitativly better than anything classical computational/complexity theory said.
You imply that I challenged this physical upper limit on state change rate in this discussion, but I did not.
My point is different. It goes down to the question about the relationship between rate of state changes on one hand, and the ability to perform a fast computation on the other hand.
The naive view is similiar to the view many cpu buyers have in regard of clocking speed. It goes along the line "The more MHz, the faster the CPU". As we know, this is not a valid measure to compare for example a Pentium IV and a PPC CPU. They are not comparable by clocking speed alone. Eg the one cpu might perform a floating point multiplication much faster than the other cpu in terms of clock cycles.
The classical theories of computation solve this problem, by mapping programs onto a very simple model of a computer, the Turing machine or register machine, or real RAM and then doing comparisions. The operations in these models are precisely defined, like incrementing a register, or decrementing a register, or testing if it is zero.
As we know there, a computation needs a certain number of basic operations as well as a certain amount of memory. Classical complexity theory tells us, how exactly memory and number of needed operations are related for these easy computation models. In fact both are subject to the "size" of the input data as well. Like I said, this only well understood for these deliberatly simple choosen computation models (Turing machines etc).
In this discussion, we were talking about limitations of computing. It makes sense to think about the most powerful computing architecture envisioned so far. And that is the model of quantumn computer at present. In this setup your computer is a quantumn mechanical system. Your input data corresponds to the initial states of the system, your computation is a measurement of the system, this meaning a physical process that kicks the system from its inital state into its final state, the final state encoding your result data.
The trick with quantumn computers is that one arranges that measurement to reduce a large number of possible solutions/states into one final state. This is decribed sometimes as doing all computations at once.
You will immediatley notice, that computation in this setup is achieved by exactly one state change, the measurement that kicks your system into final state.
Now lets translate this abstract mumbo jumbo back into real things. The first quantumn systems explored were some couple of nucleii in a big magnet, a NMR mesurement device. Initial state corresponds to some inital states of these nucleii, typically their rotational and spin degrees of freedom. Measurement means bombing these nucleii with some electromagnetic radiation and looking for the states of the nucleii after that.
What must be achieved by the experment is, that we must be able to map the input data of a problem onto the initial states of these nucleii. The output states must also correspond to a solution of the problem under consideration. Further the measurement process must correspond to the solution procedure of the problem.
As we have ttl logic gates for simple operations like AND OR NOT, researchers have to think of building quantumn logic gates. Thus systems that can handle input data with their initial states, where act of measurement corresponds to some useful operation on the input data, and the output states can be translated back into a nice result on the input data.
Question: What kind of operation can be encoded by such an experiment?
Actually I don't know. I believe however that it might be a very complex one. Take for example a chain. It just hangs down and by this finds an optimal solution to a variational problem. Or fire some photons from air into water, the travel in way, that corresponds again to the solution of a hairy differential equation. Or a chemical reaction with many molecules can solve some crazy combinatorical problem in a couple of microseconds.
The topic touched here, is the topic of representation. Everyone with a decent level of math knows, that there are different representations of the same problem, the one harder to solve, the other easier. In fact this on of the basic problem solving strategies in applied mathematics:
- find a representation where a problem is easy
- transform problem into that context
- solve problem in the easy representation
- transform problem (and solution) back
Examples are diagonalization of matrices or finding of the inverse of an integral operator (eg Green's functions in partial differential equations) by Fourier transformation, algebraic invertation, and Fourier back transformation.So in this regard I want to argue that we can choose different physical setups that might enable us to do a more or less complex computation in one state change.
So it is not only about quantity (number of states changes) but also about quality (what computation is performerd with this change).
Considering the physical theory (here: non relativistic quantumn mechanics, which is still an approximation of nature) used to derive the limitations is sufficient.
Actually short times allow for high energy fluctuations (dt * dE >= hbar), this is the very basic reasoning for the existance of short lived (so called virtual) particles in quantumn field theory, with its complications on the number of particle being not constant in physical process and the fact that one can not observe bare bone particles.
This could mean that fast processes have to deal with disturbance from such energy fluctuations, providing physical limits as well for fast computing.
What equation are you refering to?
Your example is one, that can't take advantage of parallelism. I would rather give an divide and conquer type algorithm (like sorting) as example for recursion and parallelism.
Who says that a complex problem needs a high number of state changes?
Each state change could be the result of a very high level operation, not something primitive like adding two numbers, but perhaps something like the outcome of the traveling salesman problem. Think of some clever physical setup here.
It will be due to the cleverness of the computer builders, to make most use out of the limitations.
Regards, Marc
Search for "reversible" in this article.
Not exactly that kind of bottom.
And of course it depends totally on the problem, if parallelism can be exploited.
But like writing fast or dog slow programs with a given programming language, there might be very different approaches (regarding computational power) to use the physics for building fast computers.
Thus there is a physical limit, as well as a logical limit (theories of computation and complexity) to consider.
Sorry, I meant a link found from Ralph Merckle's page. Read here.
Note that the given speed limit is on state change rate. Those states could represent much more complex operations than simple arithmetic. All in all the article is nice, but I enjoyed the one on Hans Moravec's page more, where Feynman pondered about the ultimate library. Regards, Marc
You are pulling me leg, aren't you? :)
The Japanese are probably more picky considering cleanliness than the Swiss and you tell me they show something like this between children TV?
Well they certainly don't mind showing extreme violence even for childs, but I doubt your claim.
Or a company sponsoring rape?
Very unlikely.
Not bad, troll-baku.
Or do you mean the genre of 'hentai', pornographic anime?
http://slashdot.org/article.pl?sid=01/05/27/172422 6&mode=nested
plus another link to an article of an expert system builder who wrote how a real HAL ought to work.
I must admit that I get very tired of the Slashdot submission process. I submitted a long list of entries this year, and only two or so were posted to the Slashdot frontpage.
Not that I expect that my taste is 100% compatible with the taste of the editors, but as they never give the slightest feedback, why an article was rejected, this reduces my motivation to submit IMHO interesting bits to Slashdot more and more.
The only alternative I see to Slashdot, next to establishing another service, is Kuro5hin. Alas the fellow geek crowd is centered around Slashdot. The Kuro5hin crowd, as it is these days, seems less technical/hacker to me. Less engineers, more socio/artist type of folks there.
The Kuro5hin submission process is much better, but it tends to double discussions. First matters are discussed in the pre-run mode and then stuff is moved forward to the main page, where discussion takes place a second time. This takes too much drive out of discussions, I believe.
So come on, Slashdot editors, if you reject a submission, please send an email with a word or two of explanation. It is very hard to judge from rejection alone, what is not OK with submission entries.
There is really no big difference between sniffing a telnet session with bpf and sniffing an optical or radio connected mouse or keyboard.
One solution for the telnet case was the use of encrypted channels, via the secure socket layer (SSL) and a changed protocol/tool (ssh).
It is obvious that a similiar method has to be used for the mouse/keyboard case.
So install sshd on your peripherials and be happy :-)
"That was taken after my second summer, working on the second BASIC for Microsoft. The story there is that Bob Greenberg (center right) had won a prize from a photo lab, which was a free photo shoot." So the first corporate publicity shot came about completely by chance.
The stories of these people can be found here for example.
What I fear however is lack of support from the hardware vendors. Certain hardware development like nvidia's 3d chips is driven in direct cooperation with Microsoft.
A similiar example is DVD decoding software, Apple's Quicktime, Real's line of products, Sun's Java software.
The Linux community is able to use most of these, by provided binary releases. Platforms, that are not able to make use of these binaries are left out.