Talk:Execute a Markov algorithm: Difference between revisions
→explicit vs tacit
(→Multiplication: new section) |
|||
Line 96:
::: 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).
::::: The all-at-once Markov algorithm (I assumed that J is Turing complete, because general-purpose programming languages usually are). I've now figured out the answer myself: It is. Indeed it is quite easy to write a Turing machine in it (it made me catch a bug in my C++ implementation, though). It operates the same with the all-at-once and the first-match-only version because it only operates at the head position, and there's only one head. --[[User:Ce|Ce]] 23:17, 17 December 2009 (UTC)
===Markov a specific form of Rewriting scheme?===
| |||