Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Transcomputational problem
open-in-new
<h2 id="examples">Examples</h2> <h3>Testing integrated circuits</h3> <p>Exhaustively testing all combinations of an <a href="/facts/Integrated_circuit/fjn6vg7C">integrated circuit</a> with 309 <a href="/facts/Boolean_data_type/0GWYLDoC">boolean</a> <a href="/facts/Input_(computer_science)/CulgMb3T">inputs</a> and 1 <a href="/facts/Output_(computing)/WQTE8Jas">output</a> requires testing of a total of 2309 combinations of inputs. Since the number 2309 is a transcomputational number (that is, a number greater than 1093), the problem of testing such a system of <a href="/facts/Integrated_circuit/fjn6vg7C">integrated circuits</a> is a transcomputational problem. This means that there is no way one can verify the correctness of the circuit for all combinations of inputs through <a href="/facts/Brute-force_search/YU2fzBIt">brute force</a> alone.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h3>Pattern recognition</h3> <p>Consider a <i>q</i>×<i>q</i> array of the <a href="/facts/Chessboard/BmECnjVp">chessboard</a> type, each square of which can have one of <i>k</i> <a href="/facts/Color/XDvW7ESP">colors</a>. Altogether there are <i>k</i><i>n</i> <a href="/facts/Color/XDvW7ESP">color</a> <a href="/facts/Pattern/mzD7uLQa">patterns</a>, where <i>n</i> = <i>q</i>2. The problem of determining the best classification of the patterns, according to some chosen criterion, may be solved by a search through all possible color patterns. or by many other means, which we will be ignoring here. For two colors, such a search becomes "transcomputational" when the array is 18×18 or larger. For a 10×10 array, the problem becomes transcomputational when there are 9 or more colors.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> Still, computers manage to recognize patterns in way larger arrays, thus disproving the fringe "transcomputational theory" from the early 1960s. </p><p>This has some relevance in the physiological studies of the <a href="/facts/Retina/v0ISNX2S">retina</a>. The retina contains about a million <a href="/facts/Light_sensitivity/dohEzKCm">light-sensitive</a> <a href="/facts/Cell_(biology)/bLM9UQvy">cells</a>. Even if there were only two possible states for each cell (say, an active state and an inactive state) the processing of the <a href="/facts/Retina/v0ISNX2S">retina</a> as a whole requires processing of more than 10300,000 bits of information. This is far beyond <a href="/facts/Bremermann%2527s_limit/zA4bf6sG">Bremermann's limit</a>,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and proves that humans cannot see. </p> <h3>General systems problems</h3> <p>A <a href="/facts/System/hmqQ4ASX">system</a> of <i>n</i> variables, each of which can take <i>k</i> different states, can have <i>k</i><i>n</i> possible system states. To analyze such a system, a minimum of <i>k</i><i>n</i> bits of information are to be processed. The problem becomes transcomputational when <i>k</i><i>n</i> > 1093. This happens for the following values of <i>k</i> and <i>n</i>:<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <table><tbody><tr><td><i>k</i></td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td><i>n</i></td><td>308</td><td>194</td><td>154</td><td>133</td><td>119</td><td>110</td><td>102</td><td>97</td><td>93</td></tr></tbody></table> <h2 id="implications">Implications</h2> <p>The existence of real-world transcomputational problems implies the limitations of computers as data processing tools. This point is best summarized in Bremermann's own words:<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> "The experiences of various groups who work on problem solving, theorem proving and <a href="/facts/Pattern_recognition/o1s38opj">pattern recognition</a> all seem to point in the same direction: These problems are tough. There does not seem to be a royal road or a simple method which at one stroke will solve all our problems. My discussion of ultimate limitations on the speed and amount of data processing may be summarized like this: Problems involving vast numbers of possibilities will not be solved by sheer data processing quantity. We must look for quality, for refinements, for tricks, for every ingenuity that we can think of. Computers faster than those of today will be a great help. We will need them. However, when we are concerned with problems in principle, present day computers are about as fast as they ever will be. We may expect that the technology of data processing will proceed step by step – just as ordinary technology has done. There is an unlimited challenge for ingenuity applied to specific problems. There is also an unending need for general notions and theories to organize the myriad details." <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Hypertask/WRaSPgHe">Hypertask</a></li> <li><a href="/facts/Matrioshka_brain/z7JTxY3m">Matrioshka brain</a>, a theoretical computing megastructure</li> <li><a href="/facts/Strict_finitism/UudNtdnd">Strict finitism</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Bremermann, H.J. (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93–106. <a href="http://holtz.org/Library/Natural%20Science/Physics/Optimization%20Through%20Evolution%20and%20Recombination%20-%20Bremermann%201962.htm" target="_blank">http://holtz.org/Library/Natural%20Science/Physics/Optimization%20Through%20Evolution%20and%20Recombination%20-%20Bremermann%201962.htm</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Heinz Muhlenbein. "Algorithms, data and hypotheses : Learning in open worlds" (PDF). German National Research Center for Computer Science. Retrieved 3 May 2011. <a href="http://muehlenbein.org/algo95.pdf" target="_blank">http://muehlenbein.org/algo95.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Miles, William. "Bremermann's Limit". Retrieved 1 May 2011. While the source uses 308 as the number of inputs, this number is based on an error: 2308 < 1093. <a href="http://www.wmiles.com/2010/01/bremermanns-limit" target="_blank">http://www.wmiles.com/2010/01/bremermanns-limit</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9. <a href="978-0-306-43959-9" target="_blank">978-0-306-43959-9</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Bremermann, H.J. (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93–106. <a href="http://holtz.org/Library/Natural%20Science/Physics/Optimization%20Through%20Evolution%20and%20Recombination%20-%20Bremermann%201962.htm" target="_blank">http://holtz.org/Library/Natural%20Science/Physics/Optimization%20Through%20Evolution%20and%20Recombination%20-%20Bremermann%201962.htm</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>