3 ms·
> We know that Turing machines are very limited things and that the computational processes they carry out also very limited in applicability. Again, source? D
by anyfoo 5y ago
> We know that Turing machines are very limited things and that the computational processes they carry out also very limited in applicability.
Again, source? Do you know of anything that is able to perform a computation that a Turing machine cannot?
> Just the fact that we can imagine things that can't be computed by a Turing machine should clue you in that it's probably otherwise.
Like what? Uncomputable numbers like Chaitin's constant? We can "imagine" them by stating their definition, but we cannot compute them. Or do you have something else specific in mind?
- gammalost 5y ago>Like what? The halting problem is (I think?) the standard example. Here's a short video on it https://youtu.be/macM_MtS_w4 https://youtu.be/macM_MtS_w4
- anyfoo 5y agoChaitin's constant is closely tied to the halting problem: Each bit essentially tells you if a program (in the particular order the programs are listed in the constant) halts or not. Computing every bit in there would mean knowing for every program if it halts or not, which would solve the halting problem, which we can prove is impossible. So we cannot compute that constant.
- otabdeveloper4 5y ago> Do you know of anything that is able to perform a computation that a Turing machine cannot? That's a circular argument, because "computation" is literally defined as "something that can be computed by a Turing machine". That said, the first month of the first year of a CS education is "here's these problems that can't be solved by a Turing machine, mind=blown". (At least where I studied CS, that is.)