Talk:Transcomputational problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.

Testing integrated circuits – 2^308?[edit]

MATLAB gives: , whereas . So the first integer power of 2 that is actually a transcomputational number is the 309th. This is why I change the example accordingly. --Doubaer (talk) 11:50, 23 April 2013 (UTC)

Alas, while your math appears to be correct, the source cited says 308, not 309. See WP:V and WP:OR. You need to find a reliable source that has the correct figure, then you can correct the page with a citation to your source. --Guy Macon (talk) 19:54, 23 April 2013 (UTC)
I see. However, if a formally reliable source can positively be proven wrong, shouldn't either the whole information should be completely removed, or at least a note be indicating that there is an obvious error in the cited source? --Doubaer (talk) 10:49, 8 October 2013 (UTC)
I absolutely agree. The source says "what we are saying is that 2^308 is greater than 10^93", which is not the case. Citing a source for something that is clearly wrong does not make it right. Anyway, the source still supports the statement: If 2^308 is transcomputational, then 2^309 is as well. I will go ahead and change it. --MarioS (talk) 14:37, 30 January 2014 (UTC)

[Not commenting on above (a factor of ten less is "practically" transcomputational I would think).]

What does this mean however: "Exhaustively testing all combinations of an integrated circuit with 309 inputs and 1 output requires testing of a total of 2309 combinations of inputs." I know most gates have far fewer inputs but whole chips have more "inputs" however (and more outputs). I think the number of outputs doesn't matter (more no less difficult), but can we say that testing all "realworld chips" (more pins/inputs) is impossible? Chips have structure and would this only apply in general but not for actual chips? comp.arch (talk) 11:56, 18 November 2014 (UTC)

It is an upper limit with the assumption that you know nothing about the chip being tested. Imagine that 16 of those inputs connect internally to a 16-input exclusive or gate. Once you have tested the 2^16 input combinations and confirmed that the xor gate works, you can reduce those 2^308 combinations to 2^293. likewise, you don't need to test for every memory cell interfering with every other memory cell. You can just test the ones that are close to each other and ignore the possibility that a memory cell affects another memory cell on the other side of the die (and nothing else). --Guy Macon (talk) 20:03, 21 February 2017 (UTC)

Quantum Computing[edit]

It seems quantum computing technology will take off within maybe 50 years. A quantum computer with 500 bits can simultaneously simulate all the possible configurations of a regular computer with 2^500 bits. This should be mentioned somewhere in the article. — Preceding unsigned comment added by Blurrr2 (talkcontribs) 17:57, 4 June 2014 (UTC)

That's not how quantum computing works. Not only does quantum computing not make everything magically O(1), not all algorithms speed up in the same way: see post-quantum cryptography for some discussion. -- The Anome (talk) 19:03, 21 February 2017 (UTC)

"Any number greater than 10^93 is called a transcomputational number"[edit]

The page currently opens with "a transcomputational problem is a problem that requires processing of more than 10^93 bits of information", then says, "[a]ny number greater than 10^93 is called a transcomputational number". Is this consistent? If we're talking about processing information in excess of 10^93 bits, I might expect the label "transcomputational number" apply to those numbers greater than 2^(10^93). It seems worth clarifying the discrepancy between "n bits" and "n", or correcting the description in some other way. (talk) 19:10, 28 April 2017 (UTC)