CODEWITHSUNDEEP
automataturing-machines
Sohaib Aslam
Sohaib Aslam

Reputation: 1325

Turing Machine: take a mod of two numbers?

Design a Turing machine that takes input two non-negative numbers and performs the mod operation on them, for example, mod(3,7)=3 and mod(7,3)=1. Clearly, specify any assumptions and formats about the input and output of the TM.

Upvotes: 1

Views: 6069

Answers (2)

Muhammad Kashif Arif
Muhammad Kashif Arif

Reputation: 668

some basic information is given below

![enter image description here enter image description here

complete figure is given below. here # is empty or null.Idea is same as given above. Here's how your 2 mod 3 gets processed:

#110111#
#1a0b11#
#aa0bb1#
#aa#####
#11#####

Here's how 3 mod 2 gets processed:

#111011#  
#11a0b1#
#1aa0bb#
#100011#
#a000b1#
#a######
#1######

enter image description here

Upvotes: 1

Patrick87
Patrick87

Reputation: 28322

Input is two positive integers X and Y in unary separated by a separator symbol. Output is a single number Z in unary. TM is single sided single tape deterministic.

First, move right to find the separator. Then, bounce back and forth between the end of X and the beginning of Y, marking pairs of symbols. If you run out of X before running out of Y, then X < Y and X mod Y = X; erase the separator and everything after it, then change all tape symbols to your unary digit and halt-accept. If you run out of Y before X, then change marked symbols in X to erased/separator, restore marked symbols of Y to the unary digit, and repeat (X >= Y, so X mod Y = (X - Y) mod Y).

Here's how your 2 mod 3 gets processed:

#110111#
#1a0b11#
#aa0bb1#
#aa#####
#11#####

Here's how 3 mod 2 gets processed:

#111011#
#11a0b1#
#1aa0bb#
#100011#
#a000b1#
#a######
#1######

Upvotes: 5

Related Questions