Anonymous user
Talk:Execute a Markov algorithm: Difference between revisions
→explicit vs tacit: response to C+
(→explicit vs tacit: Would the all-at-once version of the language still be Turing-complete?) |
(→explicit vs tacit: response to C+) |
||
Line 95:
::So, e.g., if you have the rules <code>baa->def, a->b</code>, then applied to the input <code>aaa</code> your result must be <code>def</code>. This was an eye-opener for me, because I would expect the result <code>bbb</code>. But then, J is an array-oriented language and likes to do things "all at once" or "in bulk", so maybe this single-match iterative approach is natural to scalar languages. --[[User:DanBron|DanBron]] 12:48, 16 December 2009 (UTC)
::: Would the all-at-once version of the language still be Turing-complete? --[[User:Ce|Ce]] 17:49, 16 December 2009 (UTC)
::::Do you mean the all-at-once version of the Markov algorithm written in J, or the all-at-once flavor of J? Certainly the all-at-once flavor of J is Turing complete (a well-known Jer implemented a Turing machine in it). I don't know about the Markov algorithm, but I suspect it is TC, because as Paddy points out, Markov is just a constricted term rewriter (which are Turing complete in general).
===Markov a specific form of Rewriting scheme?===
| |||