Ultimately, the open question here is this: are uncomputable functions just a mathematical fancy, or do there really exist processes that can only be fully correctly described by uncomputable functions?
Personally I lean towards latter view. I’m the first to admit that I have no proof. It’s just my belief, because I find the metaphysical evidence compelling. I don’t object to investigating the former possibility, but I also don’t care for it just being baldly asserted.
If the answer is affirmative, that means that science will probably never be solved and we’ll just have to content ourselves with incremental improvements in our understanding. That’s observably been the case up until now. Granted even if all processes are in fact described entirely by computable functions we might still never discover what they are.
I hope it’s clear how all that relates to the concrete problem of understanding human cognition and the brain.
I'm nowhere near smart enough to even begin to conceive of a mathematical framework for taming noncomputable functions in a pragmatic way, but I earnestly hope some genius comes along who is, supposing that noncomputable functions are needed to completely describe our reality.
Well, those functions are called uncomputable because, as far as we know, there is no repeatable way of computing them, right?
So if the human brain was able to compute functions that Turing machines can't, it doesn't mean those functions are uncomputable, it just means the Church-Turing hypothesis is false.
The Church-Turing hypothesis just means that the lambda calculus and Turing machines are isomorphic. It doesn’t actually tell us anything about reality, no matter what enthusiastic misunderstandings might say.
No, it doesn't. The Church Turing hypothesis is much stronger - it states that all real-world computation can be done by lambda calculus or Turing machines.
That's why it's a hypothesis and not a theorem - it's pretty easy to prove that lambda calculus and Turing machines are equivalent if you have the mindset of a programmer.
Put in other words, the Church Turing hypothesis is that there is no computing model higher in hierarchy than the TM and lambda-calculus.
> It doesn’t actually tell us anything about reality
Well, of course it doesn't tell is anything about reality. That's because no one managed to prove it, and I suspect no one ever will.
Ah yes. Fair enough. I confused the thesis with the hypothesis. This comes back to the begging the question I initially objected to.
Also, the notion of highest computing model is itself begging the question in the sense that the framing assumes a computational model.
So much for undergraduate philosophy. What’s your opinion? Are uncomputable functions just fanciful irrelevancies or are there processes in reality that can’t be described by computable functions? If so or if not can you propose how we might know?
I'm actually relatively confident the two are the same thing. I don't think any special name was given to the equivalency between lambda calculus and TMs.
> This comes back to the begging the question I initially objected to.
I don't think it does! Of course if someone assumes the thesis is true then they're begging the question, but I don't think that's what I am doing here, indeed :
> Also, the notion of highest computing model is itself begging the question in the sense that the framing assumes a computational model.
The definition of computation I'm using is that there exists a process somehow that can go from the input to the output. If that process can't be replicated by a TM then so be it, it just means Church-Turing is false.
Actually, the original wording that Church used was "any function that can be computed by a mathematician.." (could be computed by a TM).
So I think that it's reasonable to frame it as computation - it would be begging the question if I assumed church Turing was true.
It doesn't help that the uncomputable function definition assumes it! But in reality that a function is uncomputable doesn't actually mean there is no framework of computation that can compute it, just that a TM can't.
> So much for undergraduate philosophy. What’s your opinion? Are uncomputable functions just fanciful irrelevancies or are there processes in reality that can’t be described by computable functions? If so or if not can you propose how we might know?
I've honestly spent so much time on the question I don't even know anymore. I'm leaning towards the side that uncomputable functions can actually be computed in reality. There's an interesting paper here : https://www.sciencedirect.com/science/article/pii/S221137971... which also links to an equally interesting 2002 paper that provide theories as to how you could compute uncomputable functions in the real world (with or without blackhole evaporation), but this is still speculative because our best theories in physics are still iffy at those scales, and obviously the physics is beyond my understanding here.
Anyways, I hope this answers the question of how we might know!
> The definition of computation I'm using is that there exists a process somehow that can go from the input to the output. If that process can't be replicated by a TM then so be it, it just means Church-Turing is false.
> Actually, the original wording that Church used was "any function that can be computed by a mathematician.." (could be computed by a TM).
That explains the disconnect. My working definition of computation is essentially the one Church gives there, with the understanding that he was talking about specifically computing the exact value of some function that could also be computed with a slide rule or some other effective procedure.
> So I think that it's reasonable to frame it as computation - it would be begging the question if I assumed church Turing was true.
Even assuming C-T, it's an enthymeme and not a syllogism. The unstated leg is something roughly like "the universe is a computer." Assuming that is basically assuming what is to be proved with respect to whether or not the brain is a computer or some higher category of reckoner that happens to be able to do everything a TM can, at least with enough time, pencil, and paper.
> I'm leaning towards the side that uncomputable functions can actually be computed in reality
For clarity it would probably be sensible to use a term other than computation for determining an exact value in this case. Anyhow, I believe I follow and I lean that way too.
There's a related metaphysical question too. I'm not sure how to state it exactly, but it's implied by questions like "When I throw a ball is reality computing a parabola and applying necessary modifications?" The alternative is that whatever way reality determines how that ball moves, it's not by what we'd call an effective procedure.
> Anyways, I hope this answers the question of how we might know!
> Even assuming C-T, it's an enthymeme and not a syllogism. The unstated leg is something roughly like "the universe is a computer." Assuming that is basically assuming what is to be proved with respect to whether or not the brain is a computer or some higher category of reckoner that happens to be able to do everything a TM can, at least with enough time, pencil, and paper.
I don't think I'm making that assumption. I'm making an assumption that the process by which the brain determines outputs and inputs has some degree of repeatability - which I think is more than reasonable. Whether the brain is or isn't a computer in the classical sense of the word, there is clearly computation happening that relates inputs to outputs, right?
That is to say, if I took the same person and made them live exactly the same life (that is, everything outside how they react reacts the same way), I'd expect the outcomes as we repeat it more and more to approach some kind of distribution after a fixed amount of time t (that diverges as t gets larger exponentially). Note that this doesn't assume the presence or absence of free will, by the law of large numbers, it works either way.
From then on there is some kind of effective, repeatable procedure, so the brain does do some kind of computation. And of course that's not the only thing the brain does. But we don't need to have the universe as a computer, just the brain.
> There's a related metaphysical question too. I'm not sure how to state it exactly, but it's implied by questions like "When I throw a ball is reality computing a parabola and applying necessary modifications?" The alternative is that whatever way reality determines how that ball moves, it's not by what we'd call an effective procedure.
That's an interesting question. My attempt at an answer is that, if we were to understand the universe as a continuous process which can be defined by some kind of (recursive) semi-random, differential rules - but with maximum frequency - then yes you could say that reality is an ongoing computation. Or you could take another crack at it and think that reality is just as set of probabilities and joint probabilities that merely get (partially) sampled - in which case there isn't really any computation happening, we're just observing a tiny sliver of reality as the ball travels the probability space. There are certainly even other ways to see it. I think we it's a matter of perspective as to how you see it.
Thanks for the conversation! It is great and I've been able to develop my understanding of these concepts :)
Personally I lean towards latter view. I’m the first to admit that I have no proof. It’s just my belief, because I find the metaphysical evidence compelling. I don’t object to investigating the former possibility, but I also don’t care for it just being baldly asserted.
If the answer is affirmative, that means that science will probably never be solved and we’ll just have to content ourselves with incremental improvements in our understanding. That’s observably been the case up until now. Granted even if all processes are in fact described entirely by computable functions we might still never discover what they are.
I hope it’s clear how all that relates to the concrete problem of understanding human cognition and the brain.
I'm nowhere near smart enough to even begin to conceive of a mathematical framework for taming noncomputable functions in a pragmatic way, but I earnestly hope some genius comes along who is, supposing that noncomputable functions are needed to completely describe our reality.