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
Why does increasing the sampling rate make implementing an anti-aliasing filter easier?
Windows OS quantum vs. SQL OS Quantum
Hexagonal Grid Filling
How are one-time password generators like Google Authenticator different from having two passwords?
The concept of information structure in incomplete information games
Why was wildfire not used during the Battle of Winterfell?
What does this quote in Small Gods refer to?
Map extent same as grid for QGIS Atlas
Does the 500 feet falling cap apply per fall, or per turn?
Passport stamps art, can it be done?
What is the name of meteoroids which hit Moon, Mars, or pretty much anything that isn’t the Earth?
Why was the ancient one so hesitant to teach Dr Strange the art of sorcery
Was there a contingency plan in place if Little Boy failed to detonate?
How to get a ellipse shaped node in Tikz Network?
Is there some sort of formula to determine how many bricks I would need to build a completely new structure?
Why do Thanos' punches not kill Captain America or at least cause vital wounds?
Company stopped paying my salary. What are my options?
Extending Kan fibrations, without using minimal fibrations
Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?
When do you stop "pushing" a book?
Can 'sudo apt-get remove [write]' destroy my Ubuntu?
We are two immediate neighbors who forged our own powers to form concatenated relationship. Who are we?
Why use steam instead of just hot air?
Was the Highlands Ranch shooting the 115th mass shooting in the US in 2019
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
22911
$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
22911
$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
22911
$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
22911
asked Apr 30 at 13:24
NetHackerNetHacker
22911
edited Apr 30 at 13:45
NetHacker
asked Apr 30 at 13:24
NetHackerNetHacker
22911
asked Apr 30 at 13:24
NetHackerNetHacker
22911
asked Apr 30 at 13:24
NetHackerNetHacker
22911
22911
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,09811642
$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
6
$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,09811642
$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
6
$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,09811642
$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
6
$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,09811642
$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,09811642
edited May 3 at 7:30
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,09811642
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,09811642
answered Apr 30 at 14:40
Discrete lizard♦Discrete lizard
5,09811642
5,09811642
$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
6
$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
6
$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
6
6
$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
