3 ms·

Isn't what states "mean" irrelevant to whether it's a Turing machine? I was under the impression that as long as it can simulate a Turing machine (even an arca

Isn't what states "mean" irrelevant to whether it's a Turing machine? I was under the impression that as long as it can simulate a Turing machine (even an arcane or complicated one) is Turing complete and the state could be stored in anything (it's not like electricity has some special property that makes it better for Turing machines)

pbhjpbhj 9y ago
>it's not like electricity has some special property that makes it better for Turing machines Transmission, storage with magnetic interactions of electrical actions, small size of components, speed of transmission -- aren't these properties that make for more practical Turing machines? Parked cars are going to take ages to do anything useful with, no. (IANAComputerScientist)
- klank 9y ago
  More practical, yes. However, I believe the original poster's intent was that neither one is a "preferred" implementation from the perspective of the concept itself. There's no necessary tie between a Turing machine and electromagnetic fields. It's just that's what is easiest for us humans to use to implement it.
- lou1306 9y ago
  Keywords "practical" and "useful". No one advocates parking-lot Turing machines for actual usage, but the fact is electronics only gives you speed and size improvements, while expressiveness remains the same.
- dsp1234 9y ago
  This is just a miscommunication of what "better" means in this context. No one disputes that a modern computer implementing a Turing machine is going to calculate faster than manually manipulating MTG cards. However, better here means 'more expressive'. Turing completeness is concerned with whether or not a computational system is 'universal' or not. In other words, whether that computational system can compute everything that another computational system could. If two systems can both be shown to simulate a Turing machine, then that means that those systems could compute the same exact set of things (given enough time). So with regards to expressiveness (or the things a system could theoretically compute), since a modern computer can implement a Turing machine and a MTG game can implement a Turing machine, they are both the same, and thus neither is 'better'. In other words, the addition of electricity doesn't effect what a system could theoretically compute.
klank 9y ago
You are correct. It is precisely this ability to map seemingly arbitrary and meaningless physical manifestations of turning machines to the abstract that provides the concept so much power. By being able to provably map the implementation to the concept you're able to get all the "benefits" of the concept without having to individually prove them in your implementation where it might be really difficult or just time consuming to prove everything individually. This, coincidentally, is the same reason mathematics is so obsessed with isomorphisms, homeomorphisms, homomorphisms etc. They are all different ways of saying "this thing stays the same, even when it changes" which many times means that things proven in a place where it's easy to prove are maintained in places where it's very difficult or even impossible to prove (absent the isomorphism).

pbhjpbhj 9y ago

>it's not like electricity has some special property that makes it better for Turing machines Transmission, storage with magnetic interactions of electrical actions, small size of components, speed of transmission -- aren't these properties that make for more practical Turing machines? Parked cars are going to take ages to do anything useful with, no. (IANAComputerScientist)

klank 9y ago
More practical, yes. However, I believe the original poster's intent was that neither one is a "preferred" implementation from the perspective of the concept itself. There's no necessary tie between a Turing machine and electromagnetic fields. It's just that's what is easiest for us humans to use to implement it.
lou1306 9y ago
Keywords "practical" and "useful". No one advocates parking-lot Turing machines for actual usage, but the fact is electronics only gives you speed and size improvements, while expressiveness remains the same.
dsp1234 9y ago
This is just a miscommunication of what "better" means in this context. No one disputes that a modern computer implementing a Turing machine is going to calculate faster than manually manipulating MTG cards. However, better here means 'more expressive'. Turing completeness is concerned with whether or not a computational system is 'universal' or not. In other words, whether that computational system can compute everything that another computational system could. If two systems can both be shown to simulate a Turing machine, then that means that those systems could compute the same exact set of things (given enough time). So with regards to expressiveness (or the things a system could theoretically compute), since a modern computer can implement a Turing machine and a MTG game can implement a Turing machine, they are both the same, and thus neither is 'better'. In other words, the addition of electricity doesn't effect what a system could theoretically compute.

klank 9y ago

You are correct. It is precisely this ability to map seemingly arbitrary and meaningless physical manifestations of turning machines to the abstract that provides the concept so much power. By being able to provably map the implementation to the concept you're able to get all the "benefits" of the concept without having to individually prove them in your implementation where it might be really difficult or just time consuming to prove everything individually. This, coincidentally, is the same reason mathematics is so obsessed with isomorphisms, homeomorphisms, homomorphisms etc. They are all different ways of saying "this thing stays the same, even when it changes" which many times means that things proven in a place where it's easy to prove are maintained in places where it's very difficult or even impossible to prove (absent the isomorphism).