3 ms·
A Turing-incomplete macro system will always terminate, but it may terminate in 2 years.
by orthoxerox 6y ago
A Turing-incomplete macro system will always terminate, but it may terminate in 2 years.
- curryhoward 6y agoThat's true in practice, but technically speaking it's false. You could imagine a contrived system which is not Turing complete but still contains a (rather useless) primitive that causes an infinite loop.
- leni536 6y agoNon-Turing complete doesn't mean that you can't create too high complexity algorithms out of O(1) primitives.
- curryhoward 6y agoDid you mean to reply to a different comment? You seem to be restating the correct part of orthoxerox's comment. I was merely refuting the incorrect part.
- joshuamorton 6y agoArguably that would still terminate with an error message.
- TheCoelacanth 6y agoI don't think a Turing-incomplete language implies that programs always terminate. As a counter-example, imagine an obviously Turing-incomplete language that contains only a single instruction which simply does nothing in an infinite loop.