CODEWITHSUNDEEP
turing-machines
Behrang Behvandi
Behrang Behvandi

Reputation: 65

Markov algorithm to compute f(x)=x/2

I want to write a Markov algorithm to compute f(x)=x/2 with remainder in set А={|, , =, /}. For example if the input is |||||/||= output should be |||||/||=||*|.

Best I could get was a simple algorithm that shows the result and the remainder, but it's missing the first part where the numerator should be.

*||->|*
*|/||=+>*|
|*/||=+>|
->/||=*

Input is|||||/||= and output is /||=||*|

Upvotes: 1

Views: 620

Answers (1)

Peter Leupold
Peter Leupold

Reputation: 1212

Do not delete the | but rather mark them and then move their info to the right:

  1. The rules | -> 1# , #| -> |#, #1 -> 1# can take your initial |||||/||= to 11111#####/||=
  2. Now use your rules but consume # instead of |; I do not fully understand your notation though.
  3. If the output 11111/||=||*| is good enough for you, you can stop here. Otherwise the question is quite complicated, because the initial |||||.../|| can become arbitrarily long, and the system will not terminate if any rule is applicable to it.

Upvotes: 0

Related Questions