3 ms·

The principle you're trying to articulate is the Church-Turing thesis [1]: Every reasonable definition of computation can compute the same set of functions. [

by csense 14y ago

The principle you're trying to articulate is the Church-Turing thesis [1]: Every reasonable definition of computation can compute the same set of functions. [2] [3] [1] http://en.wikipedia.org/wiki/Church-Turing_thesis http://en.wikipedia.org/wiki/Church-Turing_thesis [2] Quantum computing may change the O() of some functions. I.e. maybe some O(n^2) problems become O(n) with a quantum computer, or NP problems become P; I'm not familiar enough with quantum computation to know for sure which classes are known to be reduced to smaller classes. But in principle you can always simulate a quantum computer on a classical computer given enough time -- of course, in practice "enough time" may be many orders of magnitude out of the realm of possibility. So quantum computation isn't a "new" form of computation as far as the Church-Turing thesis is concerned. [3] There are purely theoretical machines called "oracle machines" -- exactly like a regular computer/Turing machine, but equipped with a (theoretical) hardware device called an "oracle" which is able to solve some problem that is known to be impossible for Turing machines, like the halting problem [4]. An oracle machine can be more powerful than a Turing machine, but its violation of the Church-Turing hypothesis is sort of a technicality. Saying "Build magic hardware that does something a Turing machine can't, and attach it to a computer" is too vague about how the non-Turing computation is to be achieved to really constitute a fair definition of non-Turing computation. [4] http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem

jorgeleo 14y ago
Cool! Thank you for the links, I didn't know that it had a name, mine were just mere observation. To me it stand to logic that different hardware has different capabilities, and if an implementation can use these characteristics then the implementation can have a different O. But my point still remains that as a theorical concept, the O does not depends of the hardware in the sense that it is not a necessary piece of information to make the calculation of O. Also i would like to point that in my original definition the math paint has a purpose of utility for society. To build magic hardware would be like telling Picasso here is infinite canvas and infinite degree of colors, what can you do with them? The magic is not in the resources or the tools, the magic is in thinking independent of those tools, and then using the tools to implement. I understand that people might come from the other end of the spectrum and think that we need to begin with the tools, i just don't share that view, and it has worked for me just fine.

by csense 14y ago

jorgeleo 14y ago

Cool! Thank you for the links, I didn't know that it had a name, mine were just mere observation. To me it stand to logic that different hardware has different capabilities, and if an implementation can use these characteristics then the implementation can have a different O. But my point still remains that as a theorical concept, the O does not depends of the hardware in the sense that it is not a necessary piece of information to make the calculation of O. Also i would like to point that in my original definition the math paint has a purpose of utility for society. To build magic hardware would be like telling Picasso here is infinite canvas and infinite degree of colors, what can you do with them? The magic is not in the resources or the tools, the magic is in thinking independent of those tools, and then using the tools to implement. I understand that people might come from the other end of the spectrum and think that we need to begin with the tools, i just don't share that view, and it has worked for me just fine.