Anonymous user
Talk:Execute a Markov algorithm: Difference between revisions
→explicit vs tacit: Complaining that a task is awkward is silly
(→explicit vs tacit: Complaining that a task is awkward is silly) |
|||
Line 97:
::::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)
:::: While it might well be TC, it would also be a different algorithm; you'd have to write things differently. Solve this problem, and then maybe write the other one up as another <nowiki>{{task}}</nowiki>... –[[User:Dkf|Donal Fellows]] 10:26, 18 December 2009 (UTC)
===Markov a specific form of Rewriting scheme?===
| |||