5 ms·

The Church-Turing thesis is: "Every effectively calculable function is a computable function" [1] The definition is a little terse so we have to expand on wha

The Church-Turing thesis is: "Every effectively calculable function is a computable function" [1] The definition is a little terse so we have to expand on what "effectively calculable function" and "computable function" mean. By a "computable function", we mean a Turing machine. The term "effectively calculable function" is a little unclear but one definition that I think is the closest to the intent is "it can be done by a human without any aids except writing materials." [2]. In other words, the Church-Turing thesis is saying: "All physically computable functions are Turing computable" That is, the physical world, including human cognition, can be realized by a Turing machine. While one formulation might be cast in terms of lambda calculus, this is hiding the underlying assumption that lambda calculus is used as a proxy to simulation of the physical world and, as a subset, human cognition, effectively saying "if it can do lambda calculus, it can do the physical universe and can do human cognition". [1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Statement_in_Church's_and_Turing's_words https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#S... [2] https://en.wikipedia.org/wiki/Effective_method#Definition https://en.wikipedia.org/wiki/Effective_method#Definition

rutherblood 6y ago
"That is, the physical world, including human cognition, can be realized by a Turing machine." How did you get to the conclusion that all physical world is computable? Rather a huge jump i would say. Sure some things are, but "all of it" would rather be a BIG assumption. Physical theories of the world are limited to our current state of observations and knowledge of the world, they AREN'T the actual world. Who is to say this continuous search, observation and refinement of theories will ever end and we'll have a FINAL theory of everything that we can then plug into a computer and simulate? Sure you can now say "I don't require a theory of everything, I just need a "sufficient" amount of theory to simulate the part of the world from which I can have my intelligence & cognition emerge". Sure you can say that but that would again hinge on the assumption that such cognition is reducable to these "sufficient" laws. Likewise saying that the whole physical world can be realized by a Turung machine is a bit rich when we don't even know if such a complete reduction of the physical world is possible and when such reduction to physical laws is surely not yet complete. EDIT: grammar
- xyzzyz 6y ago
  How did you get to the conclusion that all physical world is computable? That’s not the conclusion, that’s the whole thesis. The whole point of it is that yes, it’s not provable, but so far we haven’t seen anything to suggest the contrary. All of our current physical theories are very much computable, for example.
  - deleted 6y ago
    [deleted]
  - rutherblood 6y ago
    My point is not whether all physical laws are computable, I have no doubt they are insofar as these laws are expressed mathematically. My point is rather that this search for laws might never finish and a complete ruleset never come about. Like I said all current theories are based on current state of observations. Who is to say we don't observe something in the future for which these laws need to be revised? Who is to say this doesn't keep happening indefinitely? If such a "bottoming out" cannot even be conceived of, saying that the physical world, even a part of it, is exactly computable AS IT IS (all aspects of it) is utmost arrogance. What do we know about the brain? how does it generate cognition? why does the color 'red' look like the way it does to you; does it look like the same to me? Unless the nature of such cognition and such a being which embodies this cognition is known one cannot say it is reducible or "emergent" from the CURRENT set or even any FUTURE set of physical laws we know or will know about. The map is not the territory however minute in detail it becomes. Sure this map can become the territory itself by becoming it but then we cease to call it a "map". Say you want to understand how pendulums work, you make a pendulum, play with it. No one's going to call this actual pendulum a "simulation".
  - mcprwklzpq 6y ago
    Church-Turing thesis is that for every algorithm you can compute you can define a turing machine that can compute it too. You still have show that you can compute answers to your questions about physical world or human cognition. And we know that we can define an infinite amount of problems that can not ever be computed (or else you can for example solve the halting problem). So there would be infinite amount of questions about the world that we can not ever answer. And there would be more questions that we can not answer (they are uncountable) than we can answer (they are countable). So if you have a question - chances are such that it can never be answered. edit: more likely never can be answered.
orbifold 6y ago
In might be computable in principle but not in practice for a long time, similar to how it is possible to simulate all molecules of air in one cubic meter (neglecting quantum effects), but not actually feasible in practice. Any argument for computability all needs an argument why a "coarse graining" or "effective model" of the underlying physical system exists. In the case of transistors that is because all that matters are binary stable states, which reliably abstract over the complicated device physics. In the case of biological cells and neurons in the brain it is much less obvious what the reliable abstraction is. Right now a lot points towards "it is just a bunch of linear algebra and lots of data", but especially when we come to things like memory, online and few shot learning, the answer becomes far less obvious.

rutherblood 6y ago

"That is, the physical world, including human cognition, can be realized by a Turing machine." How did you get to the conclusion that all physical world is computable? Rather a huge jump i would say. Sure some things are, but "all of it" would rather be a BIG assumption. Physical theories of the world are limited to our current state of observations and knowledge of the world, they AREN'T the actual world. Who is to say this continuous search, observation and refinement of theories will ever end and we'll have a FINAL theory of everything that we can then plug into a computer and simulate? Sure you can now say "I don't require a theory of everything, I just need a "sufficient" amount of theory to simulate the part of the world from which I can have my intelligence & cognition emerge". Sure you can say that but that would again hinge on the assumption that such cognition is reducable to these "sufficient" laws. Likewise saying that the whole physical world can be realized by a Turung machine is a bit rich when we don't even know if such a complete reduction of the physical world is possible and when such reduction to physical laws is surely not yet complete. EDIT: grammar

xyzzyz 6y ago
How did you get to the conclusion that all physical world is computable? That’s not the conclusion, that’s the whole thesis. The whole point of it is that yes, it’s not provable, but so far we haven’t seen anything to suggest the contrary. All of our current physical theories are very much computable, for example.
- deleted 6y ago
  [deleted]
- rutherblood 6y ago
  My point is not whether all physical laws are computable, I have no doubt they are insofar as these laws are expressed mathematically. My point is rather that this search for laws might never finish and a complete ruleset never come about. Like I said all current theories are based on current state of observations. Who is to say we don't observe something in the future for which these laws need to be revised? Who is to say this doesn't keep happening indefinitely? If such a "bottoming out" cannot even be conceived of, saying that the physical world, even a part of it, is exactly computable AS IT IS (all aspects of it) is utmost arrogance. What do we know about the brain? how does it generate cognition? why does the color 'red' look like the way it does to you; does it look like the same to me? Unless the nature of such cognition and such a being which embodies this cognition is known one cannot say it is reducible or "emergent" from the CURRENT set or even any FUTURE set of physical laws we know or will know about. The map is not the territory however minute in detail it becomes. Sure this map can become the territory itself by becoming it but then we cease to call it a "map". Say you want to understand how pendulums work, you make a pendulum, play with it. No one's going to call this actual pendulum a "simulation".
- mcprwklzpq 6y ago
  Church-Turing thesis is that for every algorithm you can compute you can define a turing machine that can compute it too. You still have show that you can compute answers to your questions about physical world or human cognition. And we know that we can define an infinite amount of problems that can not ever be computed (or else you can for example solve the halting problem). So there would be infinite amount of questions about the world that we can not ever answer. And there would be more questions that we can not answer (they are uncountable) than we can answer (they are countable). So if you have a question - chances are such that it can never be answered. edit: more likely never can be answered.

orbifold 6y ago

In might be computable in principle but not in practice for a long time, similar to how it is possible to simulate all molecules of air in one cubic meter (neglecting quantum effects), but not actually feasible in practice. Any argument for computability all needs an argument why a "coarse graining" or "effective model" of the underlying physical system exists. In the case of transistors that is because all that matters are binary stable states, which reliably abstract over the complicated device physics. In the case of biological cells and neurons in the brain it is much less obvious what the reliable abstraction is. Right now a lot points towards "it is just a bunch of linear algebra and lots of data", but especially when we come to things like memory, online and few shot learning, the answer becomes far less obvious.