2 ms·
That's not my point. Any Turing machine can't necessarily emulate any other Turing machine.
by shakna 9y ago
That's not my point. Any Turing machine can't necessarily emulate any other Turing machine.
- Dylan16807 9y agoAs far as storage goes, I understand and disagree with your point in practical terms. Every computer we use is 99.9% identical to a universal Turing machine, because the amount of storage available is functionally identical to infinite.
- shakna 9y agoI can't agree with that. Limits do indeed exist. In cases like the article, hard limits exist and can require effort to work around. It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Other limits exist as well, such as the number of reads or writes that can take place before hardware decays. Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. But a universal Turing machine could. Not all machines are equal.
- Dylan16807 9y agoYou can glue a micro SD card to almost anything. And if you're executing anything in a Turing-machine-like manner, one microSD will probably last you the lifetime of the machine. Even if you're not, for just about any problem it's trivial to divert 1% of the budget into buying more microSD cards. > Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. Why would damage occur? I'm confused. > It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Since we're comparing to a Turing machine, I think it's fair to demand that all input be in the form of rewritable storage. Let's say no more than half-full to start with. It's pretty tricky to think of a problem like this where using a low-memory algorithm will run out. You can always recompute temporary data instead of storing it.
- shakna 9y ago> You can glue a micro SD card to almost anything. Your answer to the claim that resources are finite... Is that added resources negates that? > Why would damage occur? I'm confused. EEPROM is limited to about 100,000 writes. SD cards to about 150,000 writes. After that you have physical failure. > t's pretty tricky to think of a problem like this where using a low-memory algorithm will run out. This just sounds intentionally obtuse. If the memory was good enough to be treated infintely, why do you select a low-memory algorithm? Why not a high-memory program? Remember: My claim was not every Turing machine can emulate every other.
- Dylan16807 9y ago> Your answer to the claim that resources are finite... Is that added resources negates that? Not merely that you can add resources. That you can add enough resources to emulate a Turing machine for nearly zero cost. In other words: There is no real-world project where you want to emulate a Turing machine and can't. You have to be artificially limiting yourself. Lack of Turing-completeness causes zero problems in practice. Machines that don't have enough storage to do a job? Happens all the time. But that's because the requirements for the job go far beyond mere Turing-completeness. They require actual performance metrics. > If the memory was good enough to be treated infintely, why do you select a low-memory algorithm? Why not a high-memory program? > Remember: My claim was not every Turing machine can emulate every other. A cheap blob of memory can let you emulate a Turing machine practically forever, but you do have to manage it with care. It's infinite to the machine being emulated inside the sandbox. It's not infinite outside of the sandbox. If the Turing machine to be emulated is high-memory, go for it. You could run that emulation for the lifetime of the machine.
- shakna 9y ago> That you can add enough resources to emulate a Turing machine for nearly zero cost. > In other words: There is no real-world project where you want to emulate a Turing machine and can't. You have to be artificially limiting yourself. Lack of Turing-completeness causes zero problems in practice. That, is frankly ridiculous. Mostly because of the next quote. > Machines that don't have enough storage to do a job? Happens all the time. That's a lack of universality. It causes such an issue we run data centers to work around the problems. You can't always keep adding memory. If we had universality, memory would be no issue. If memory is no issue, cache misses wouldn't exist, and memory optimisation wouldn't exist either. The halting problem would be solved overnight, and we'd be able to abolish all safety issues in programs because we'd be able to formally solve the entire program. Or we wouldn't end up with stories such as Amazon running out of provisioning space [0]. > If the Turing machine to be emulated is high-memory, go for it. You could run that emulation for the lifetime of the machine. The lifetime of the machine... Which is less than that which it is emulated. --- Allow me to try and summarise. I pointed out merely that, technically, we don't have universal Touring machines. You argue that resources can always be added, thus we may as well have them. That no "real world" problem suffers from the fact that memory is limited. Yet, companies like Amazon, nVidia, AMD & Intel spent millions in R&D attempting to work around the very limitations that universality creates. [0] https://www.channelweb.co.uk/crn-uk/news/3007237/amazon-running-out-of-cloud-space-was-a-surprise-says-uk-user https://www.channelweb.co.uk/crn-uk/news/3007237/amazon-runn...