3 ms·

> What if they are not able to do so? Good question! Since you have already corrected one of my mistakes, I don't want to start off by disagreeing lol In my

> What if they are not able to do so? Good question! Since you have already corrected one of my mistakes, I don't want to start off by disagreeing lol In my head, this is just a silly word problem, the purpose of which is to show the mathematical theory of computation requires a new axiom Here is a map which describes my idea: Party with infinite number of mathematicians --> theory of computation a mathematician --> Turing Machine getting a new piece of paper --> a new axiom that gives Turing Machines a new self-replication feature According to this new theory of computation which I am trying to invent, and which I have named The Theory of Self Reproducing Machines, it would not be an issue that "because the number of new people you can reach within a minute goes from quadratic towards linear" As a counter example to your idea: consider twitter and the abstract concept of a social network graph where it's quite possible to send messages instantly for all practical purposes Curious for your thoughts

eesmith 7y ago
If you have access to an infinite number of CPUs then every problem can be solved in finite time. This is clearly obvious conclusion (excepting perhaps problems which involve transfinite numbers, in which case you need to pin down which infinity you mean). In the real world, communication is limited to the speed of light. If your message is going out to the "infinite number of mathematicians", then after time T your message reaches 4/3 π (c*T)^3 of space, which is polynomial in time. You therefore cannot contact an exponential number of mathematicians, which is what you would need in order to demonstrate the trivial reduction of an NP problem into P. See https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation for other real-world limitations. You mention "twitter ... where it's quite possible to send messages instantly for all practical purposes." There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources. (Any finite number of people/CPUs will be a problem, even if the entire galaxy were populated by humans and/or computronium) Consider https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numb... with the famous description attributed to Erdős: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. Even with the entire mathematical population of the world working on it, Erdős doesn't think R(6, 6) solvable in reasonable time. Now try solving R(n, n). Can it really be solved in linear time even if the entire world becomes proficient in mathematics?
- calhoun137 7y ago
  How interesting. You have given me quite a lot to think about it. I am still unable to get past the following, but I will continue to consider everything you have said in our discussion very carefully. Issue: I carried out theoretical physics energy calculations on the work done by cells as a result of cell self-replication in the human nervous system (recall the nervous system primarily functions to send signals at ~the speed of light from one part of the body to another) The thing I am unable to get past for arguments of the type you made, e.g. when you stated: > "There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources" The issue is: the human body does not completely fall apart, it all works fine and there are no issues like this, there is some kind of bound from being a physical object in the real world, but physically and quite practically for all purposes the human nervous system is capable of expending an exponential amount of energy Question: Since the human body does not fall apart despite the fact that its doing cell self-replication, given how theoretical physics shows there truly is an exponential level of energy expended during cell-replication, how are these types of issues that you raise, quite legitimately from a pure-math/theoretical comp-sci perspective, not also a major issue for the human nervous system? Thanks again! This discussion has been enlightening
  - eesmith 7y ago
    The nervous system does not work at the speed of light. https://en.wikipedia.org/wiki/Nerve_conduction_velocity https://en.wikipedia.org/wiki/Nerve_conduction_velocity says: > Nerve impulses are extremely slow compared to the speed of electricity, ... however, it is very fast compared to the speed of blood flow, with some myelinated neurons conducting at speeds up to 120 m/s (432 km/h or 275 mph). > the human nervous system is capable of expending an exponential amount of energy I don't know what that means. Exponent in what dimension? Time? What's the exponent? Do you have any demonstrable evidence? At some point the human nervous system will be limited by the amount of food needed. The Tour de Frace cyclists consume some 7000 food calories per day. Another limit is the need to keep cool, because that consumed power must go somewhere. > given how theoretical physics shows there truly is an exponential level of energy expended during cell-replication Here again you'll need to explain what you mean. 1.0 is an exponent, so in some since you are trivially correct. But I strongly suspect that's not what you meant. I think you mean that at the beginning there is 1 cell, the zygote, then 2, then 4, etc. But this exponential growth phase is short. It must be, otherwise it would quickly consume all available energy in its environment. > not also a major issue for the human nervous system? Again, I don't follow. I am not aware of humans being able to solve NP-hard problems in polynomial time. We certainly can solve some NP-hard problems when N is small, but how do you know it scales polynomially?

eesmith 7y ago

If you have access to an infinite number of CPUs then every problem can be solved in finite time. This is clearly obvious conclusion (excepting perhaps problems which involve transfinite numbers, in which case you need to pin down which infinity you mean). In the real world, communication is limited to the speed of light. If your message is going out to the "infinite number of mathematicians", then after time T your message reaches 4/3 π (c*T)^3 of space, which is polynomial in time. You therefore cannot contact an exponential number of mathematicians, which is what you would need in order to demonstrate the trivial reduction of an NP problem into P. See https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation for other real-world limitations. You mention "twitter ... where it's quite possible to send messages instantly for all practical purposes." There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources. (Any finite number of people/CPUs will be a problem, even if the entire galaxy were populated by humans and/or computronium) Consider https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numb... with the famous description attributed to Erdős: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. Even with the entire mathematical population of the world working on it, Erdős doesn't think R(6, 6) solvable in reasonable time. Now try solving R(n, n). Can it really be solved in linear time even if the entire world becomes proficient in mathematics?

calhoun137 7y ago
How interesting. You have given me quite a lot to think about it. I am still unable to get past the following, but I will continue to consider everything you have said in our discussion very carefully. Issue: I carried out theoretical physics energy calculations on the work done by cells as a result of cell self-replication in the human nervous system (recall the nervous system primarily functions to send signals at ~the speed of light from one part of the body to another) The thing I am unable to get past for arguments of the type you made, e.g. when you stated: > "There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources" The issue is: the human body does not completely fall apart, it all works fine and there are no issues like this, there is some kind of bound from being a physical object in the real world, but physically and quite practically for all purposes the human nervous system is capable of expending an exponential amount of energy Question: Since the human body does not fall apart despite the fact that its doing cell self-replication, given how theoretical physics shows there truly is an exponential level of energy expended during cell-replication, how are these types of issues that you raise, quite legitimately from a pure-math/theoretical comp-sci perspective, not also a major issue for the human nervous system? Thanks again! This discussion has been enlightening
- eesmith 7y ago
  The nervous system does not work at the speed of light. https://en.wikipedia.org/wiki/Nerve_conduction_velocity https://en.wikipedia.org/wiki/Nerve_conduction_velocity says: > Nerve impulses are extremely slow compared to the speed of electricity, ... however, it is very fast compared to the speed of blood flow, with some myelinated neurons conducting at speeds up to 120 m/s (432 km/h or 275 mph). > the human nervous system is capable of expending an exponential amount of energy I don't know what that means. Exponent in what dimension? Time? What's the exponent? Do you have any demonstrable evidence? At some point the human nervous system will be limited by the amount of food needed. The Tour de Frace cyclists consume some 7000 food calories per day. Another limit is the need to keep cool, because that consumed power must go somewhere. > given how theoretical physics shows there truly is an exponential level of energy expended during cell-replication Here again you'll need to explain what you mean. 1.0 is an exponent, so in some since you are trivially correct. But I strongly suspect that's not what you meant. I think you mean that at the beginning there is 1 cell, the zygote, then 2, then 4, etc. But this exponential growth phase is short. It must be, otherwise it would quickly consume all available energy in its environment. > not also a major issue for the human nervous system? Again, I don't follow. I am not aware of humans being able to solve NP-hard problems in polynomial time. We certainly can solve some NP-hard problems when N is small, but how do you know it scales polynomially?