4 ms·

I think I agree with you, but maybe not for reasons you agree with. You see, the Turing Machine is a Form, in Plato's sense. I can formulate all of the programs

I think I agree with you, but maybe not for reasons you agree with. You see, the Turing Machine is a Form, in Plato's sense. I can formulate all of the programs and machines imaginable (at this current moment in our lifetime) with Turing's process for creating machines. The individual machines created from his process may not be able to run Turing-complete code, e.g. a calculator formalized as a Turing Machine. But our machines, our computers, are machines which can accept other machines as input. And even in this limited domain we cannot solve the Halting Problem, so I consider them a part of the Turing Machine class even if they are descendants of Turing's Form. Edit: In more concrete terms, one can design a very simple program in C, but that doesn't mean that C isn't capable of being used to design more complicated programs. It also isn't very useful to measure a _specific_ C program, especially a simple one, as a measure of what _all_ C programs may be able to do. Edit^2: After thinking about this more, I think a better argument is this: it is true that our physical machines must exist in some sort of finite state, but if our big problems (such as the Halting Problem) were merely symptoms of infinity, then we would have solved them by now in our limited and finite domain.

yarg 3y ago
> And even in this limited domain we cannot solve the Halting Problem, so I consider them a part of the Turing Machine class even if they are descendants of Turing's Form. Non-halting finite machines are periodic. The fact that we are unable to detect that they have returned to a prior state is a physical limitation, not a theoretical one.
russdill 3y ago
Ok, if you want to create your own definitions and describe how they fit together, that's fine. I was speaking of the formal definitions of computability complexity classes, so I think we were speaking past each other a bit.
- leroy-is-here 3y ago
  I think your hang-up is one of infinity. Just because we must deal the reality of the finite does not mean our computers are not _capable_. For example, the Turing Machine in our minds is able to run infinitely, but the computer plugged in to my wall cannot because it is dependent on me paying the power bill. Any Turing Machine we will have made into silicon is able to run any Turing Machine we can formulate (at this current moment in time) except only up to a finite point. But we can forever increase that finite point of measure! For example, our computers now may be able to calculate up to N. The next year, we may be able to do N+10000. The following year, N+10000000, and on and on. This is a limit of our reality, but not of the Turing Machine, which our machines must be because they are capable of being extended all the way to infinity, even if we take them there step by step, by adding 1 at a time. Again, if this were a problem of infinity, then we would have limited the domain and solved the issue already. But we can design very simple, very finite Turing Machine programs for which the Halting Problem cannot be solved: while (true) { sleep(1); } edit: you were right -- we are talking past each other. The "finite" in "finite state machine" is not useful here. Any infinite Turing Machine which we have made into silicon is still an infinite Turing Machine, just one we have inherently limited due to our realities of only having so much time or room or resources or whatever else. But a FSM is not one we limited artificially, it is a different class entirely and a class we can completely make into silicon without any sort of loss. Again, if this were a problem of "infinity" then we would have limited the domain by our own choice and solved it, which we have done for machines of a lower complexity, but _not_ for Turing Machines.
  - russdill 3y ago
    You're pointing out that a machine that can grow without bound is mathematically equivalent to an infinite one. There's a reason the word "finite" is part of "finite state machine". If you have a state machine that can grow without bound, it's not an FSM and is capable of computing things an FSM cannot compute. And the halting problem is solvable for any finite machine. A finite machine has a finite number of states. You only need to run N steps where N is the number of possible states. If it hasn't halted at that point, it must run forever.
    - yarg 3y ago
      > You only need to run N steps where N is the number of possible states. It's at most N steps - the machine can return to a prior state long before that happens, which would also prove that it's non-halting. Of course the memory requirements to do that make it purely theoretical - but so too is exhaustive execution (due to time requirements). https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_lower_bounds https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_l...
      - deleted 3y ago
        [deleted]

yarg 3y ago

> And even in this limited domain we cannot solve the Halting Problem, so I consider them a part of the Turing Machine class even if they are descendants of Turing's Form. Non-halting finite machines are periodic. The fact that we are unable to detect that they have returned to a prior state is a physical limitation, not a theoretical one.

russdill 3y ago

Ok, if you want to create your own definitions and describe how they fit together, that's fine. I was speaking of the formal definitions of computability complexity classes, so I think we were speaking past each other a bit.

leroy-is-here 3y ago
I think your hang-up is one of infinity. Just because we must deal the reality of the finite does not mean our computers are not _capable_. For example, the Turing Machine in our minds is able to run infinitely, but the computer plugged in to my wall cannot because it is dependent on me paying the power bill. Any Turing Machine we will have made into silicon is able to run any Turing Machine we can formulate (at this current moment in time) except only up to a finite point. But we can forever increase that finite point of measure! For example, our computers now may be able to calculate up to N. The next year, we may be able to do N+10000. The following year, N+10000000, and on and on. This is a limit of our reality, but not of the Turing Machine, which our machines must be because they are capable of being extended all the way to infinity, even if we take them there step by step, by adding 1 at a time. Again, if this were a problem of infinity, then we would have limited the domain and solved the issue already. But we can design very simple, very finite Turing Machine programs for which the Halting Problem cannot be solved: while (true) { sleep(1); } edit: you were right -- we are talking past each other. The "finite" in "finite state machine" is not useful here. Any infinite Turing Machine which we have made into silicon is still an infinite Turing Machine, just one we have inherently limited due to our realities of only having so much time or room or resources or whatever else. But a FSM is not one we limited artificially, it is a different class entirely and a class we can completely make into silicon without any sort of loss. Again, if this were a problem of "infinity" then we would have limited the domain by our own choice and solved it, which we have done for machines of a lower complexity, but _not_ for Turing Machines.
- russdill 3y ago
  You're pointing out that a machine that can grow without bound is mathematically equivalent to an infinite one. There's a reason the word "finite" is part of "finite state machine". If you have a state machine that can grow without bound, it's not an FSM and is capable of computing things an FSM cannot compute. And the halting problem is solvable for any finite machine. A finite machine has a finite number of states. You only need to run N steps where N is the number of possible states. If it hasn't halted at that point, it must run forever.
  - yarg 3y ago
    > You only need to run N steps where N is the number of possible states. It's at most N steps - the machine can return to a prior state long before that happens, which would also prove that it's non-halting. Of course the memory requirements to do that make it purely theoretical - but so too is exhaustive execution (due to time requirements). https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_lower_bounds https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_l...
    - deleted 3y ago
      [deleted]