Thanks, I needed the refresher. I’d listened the talk and skimmed the paper not too long ago but couldn’t recall the main point without the summary in the top answer: A feature adds power if it would require a global transformation to emulate.
The whole thing’s pointless and indicative of CS navel-gazing, since there are Real-World problems that can’t be handled by a Turing Machine.
For example, if you have two independent tasks and want to switch contexts, then you need to record the current tape position. Since the tape is of infinite length, that will require an infinitely-long label (i.e. an infinite number of digits etc.). But since the control unit is finite, it can’t be stored there.
The concept of a Turing Machine is fine for discussing algorithms. But Real World languages need to do far more.
This submission is not about tape-driven Turing machines. They’re mentioned in one answer (not the top one, and they’re not the main point even of the one that mentions them) and in one or two comments; the main content is about actual, real-world programming languages, and far from being ‘CS navel-gazing’, it does mention a real-world application.
Yeah. The obvious relevance is to compilers, though there’s the caveat that compiler targets are usually highly expressive so it’s rare to need a global transformation to compile a target to a lower level of expressiveness. But it does happen for restricted targets such as Wasm.
For example, if you have two independent tasks and want to switch contexts, then you need to record the current tape position. Since the tape is of infinite length, that will require an infinitely-long label (i.e. an infinite number of digits etc.). But since the control unit is finite, it can’t be stored there.
Maybe I’m misunderstanding, can’t the bookmark just be a unique symbol on the tape? With all the usual techniques you can handle this without increasing the alphabet size, though it isn’t very efficient it doesn’t seem particularly impossible.
Reposting because the responses to this submission strongly suggest Lobsters could do with a refresher on it (or on the original paper) ;-)
Thanks, I needed the refresher. I’d listened the talk and skimmed the paper not too long ago but couldn’t recall the main point without the summary in the top answer: A feature adds power if it would require a global transformation to emulate.
The whole thing’s pointless and indicative of CS navel-gazing, since there are Real-World problems that can’t be handled by a Turing Machine.
For example, if you have two independent tasks and want to switch contexts, then you need to record the current tape position. Since the tape is of infinite length, that will require an infinitely-long label (i.e. an infinite number of digits etc.). But since the control unit is finite, it can’t be stored there.
The concept of a Turing Machine is fine for discussing algorithms. But Real World languages need to do far more.
This submission is not about tape-driven Turing machines. They’re mentioned in one answer (not the top one, and they’re not the main point even of the one that mentions them) and in one or two comments; the main content is about actual, real-world programming languages, and far from being ‘CS navel-gazing’, it does mention a real-world application.
Yeah. The obvious relevance is to compilers, though there’s the caveat that compiler targets are usually highly expressive so it’s rare to need a global transformation to compile a target to a lower level of expressiveness. But it does happen for restricted targets such as Wasm.
Maybe I’m misunderstanding, can’t the bookmark just be a unique symbol on the tape? With all the usual techniques you can handle this without increasing the alphabet size, though it isn’t very efficient it doesn’t seem particularly impossible.