4 ms·
I don't think Turing-completeness implies any issues when converting programs between equally powerful automata. In fact, a lot of results in the theory of auto
by NotOscarWilde 5y ago
I don't think Turing-completeness implies any issues when converting programs between equally powerful automata. In fact, a lot of results in the theory of automata / early computational complexity take a form of converting all programs of machine A -- in fact the machine itself -- in order to run it on machine B.
- DemocracyFTW 5y agoIn theory there should be no difference between theory and practice, but in practice there often is. TeX's syntax itself being Turing-complete means you can barely start to do static analysis on the code before hitting a wall you can only get over by installing a huge fraction of the ~1GB download that is TeXLive. "Being theoretically possible" is in no way orthogonal to "impractical in many or most circumstances".
- GiovanniP 5y agoPlease take a look at the following comments thread https://news.ycombinator.com/item?id=27820466 https://news.ycombinator.com/item?id=27820466, in particular at https://news.ycombinator.com/item?id=27822662 https://news.ycombinator.com/item?id=27822662 where Massimiliano Gubinelli (one of the main TeXmacs developers) explains the issue.