Does this article imply that Turing-Computability is not the same as “effectively computable”?Time complexity version of the Church-Turing ThesisQuantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?Analog computers and the Church-Turing thesisIs a partial function Turing-computable?Church-Turing thesis is a dualismDoes Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?weak Church-Turing thesisChurch-Turing Thesis and computational power of neural networksChurch-Turing thesis and hypercomputation?Empirical evidence for the Church-Turing thesis in other disciplines
Copy previous line to current line from text file
To kill a cuckoo
How long would it take for people to notice a mass disappearance?
Has the Hulk always been able to talk?
Is there precedent or are there procedures for a US president refusing to concede to an electoral defeat?
Can you use "едать" and "игрывать" in the present and future tenses?
As a GM, is it bad form to ask for a moment to think when improvising?
Is 'contemporary' ambiguous and if so is there a better word?
Which sphere is fastest?
Why is my arithmetic with a long long int behaving this way?
What do "Sech" and "Vich" mean in this sentence?
Is there a word that describes the unjustified use of a more complex word?
A factorization game
Using Im[] and Re[] Correctly
How should I tell my manager I'm not paying for an optional after work event I'm not going to?
Would you use "llamarse" for an animal's name?
Any examples of liquids volatile at room temp but non-flammable?
When does tabularx decide to break the cell entry instead of reducing the columns separation?
What to use instead of cling film to wrap pastry
Prove that a definite integral is an infinite sum
My first c++ game (snake console game)
Handling Null values (and equivalents) routinely in Python
Why is "breaking the mould" positively connoted?
When an imagined world resembles or has similarities with a famous world
Does this article imply that Turing-Computability is not the same as “effectively computable”?
Time complexity version of the Church-Turing ThesisQuantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?Analog computers and the Church-Turing thesisIs a partial function Turing-computable?Church-Turing thesis is a dualismDoes Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?weak Church-Turing thesisChurch-Turing Thesis and computational power of neural networksChurch-Turing thesis and hypercomputation?Empirical evidence for the Church-Turing thesis in other disciplines
$begingroup$
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, are physically buildable.
turing-machines quantum-computing church-turing-thesis
asked Apr 30 at 13:24
NetHackerNetHacker
22411
$endgroup$
add a comment |
$begingroup$
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, are physically buildable.
turing-machines quantum-computing church-turing-thesis
asked Apr 30 at 13:24
NetHackerNetHacker
22411
$endgroup$
add a comment |
$begingroup$
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, are physically buildable.
turing-machines quantum-computing church-turing-thesis
asked Apr 30 at 13:24
NetHackerNetHacker
22411
$endgroup$
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, are physically buildable.
turing-machines quantum-computing church-turing-thesis
turing-machines quantum-computing church-turing-thesis
asked Apr 30 at 13:24
NetHackerNetHacker
22411
asked Apr 30 at 13:24
NetHackerNetHacker
22411
edited Apr 30 at 13:45
NetHacker
asked Apr 30 at 13:24
NetHackerNetHacker
22411
asked Apr 30 at 13:24
NetHackerNetHacker
22411
asked Apr 30 at 13:24
NetHackerNetHacker
22411
22411
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.
Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.
Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.
Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
$endgroup$
add a comment |
$begingroup$
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, all problems that we consider are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
$endgroup$
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f108757%2fdoes-this-article-imply-that-turing-computability-is-not-the-same-as-effectivel%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.
Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.
Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.
Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
$endgroup$
add a comment |
$begingroup$
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.
Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.
Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.
Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
$endgroup$
add a comment |
$begingroup$
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.
Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.
Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.
Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
$endgroup$
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.
Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.
Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.
Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
edited Apr 30 at 21:08
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
answered Apr 30 at 19:34
AcccumulationAcccumulation
28415
28415
add a comment |
add a comment |
$begingroup$
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, all problems that we consider are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
$endgroup$
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
add a comment |
$begingroup$
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, all problems that we consider are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
$endgroup$
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
add a comment |
$begingroup$
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, all problems that we consider are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
$endgroup$
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, all problems that we consider are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
edited 16 hours ago
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,05811541
5,05811541
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
add a comment |
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
$begingroup$
But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."?
$endgroup$
– NetHacker
Apr 30 at 15:30
5
5
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
$begingroup$
Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer.
$endgroup$
– Discrete lizard♦
Apr 30 at 15:41
1
1
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
$begingroup$
@NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve".
$endgroup$
– Delioth
Apr 30 at 21:30
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f108757%2fdoes-this-article-imply-that-turing-computability-is-not-the-same-as-effectivel%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
