Create a 3-tape Turing machine that implements multiplication with binary numbers. The first tape and the...

Create a 3-tape Turing machine that implements multiplication with binary numbers. The first tape and the second tape hold the numbers being multiplied and the third tape holds the product of the first two tapes. The two binary numbers may be different lengths.

Solutions

Expert Solution

Steps:

Step-1. First ignore 0’s, C and go to right & then if B found convert it into C and go to left.

Step-2. Then ignore 0’s and go left & then convert C into C and go right.

Step-3. Then convert all X into X and go right if 0 found convert it into X and go to left otherwise if C found convert it into B and go to right and stop the machine.

Step-4. If then X found convert it into X and go left then C into C and left then Y into Y and left.

Step-5. Then if B found convert it into B and right then if Y into 0 and right or if C into C and right and go to step 3 and repeat the process otherwise if 0 found after 4th step then convert it into Y and right then Y into Y and right then C into C and right then 0 into 0 or X into X and right then C into C and right then 0 into 0 and right then B into 0 and left then 0 into 0 and left then C into C and left then 0 into 0 or X into X and left then C into C and left.

venereology answered 4 months ago

Next > < Previous

Related Solutions

Turing machine A that does the following: • On its first and second tape, A receives...

Turing machine A that does the following: • On its first and second tape, A receives two strings w and v, w, v ∈ {0, 1}? , representing two integer numbers. When machine A is started, the tape heads are located on the left-most position, on the most significant bits of w and v. • If none of the inputs w and v is the empty word, the Turing machine A writes the binary representation of the sum of the...

Explain how a Turing Machine can simulate an arbitrary DFA. Use a 2-tape Turing Machine. It...

Explain how a Turing Machine can simulate an arbitrary DFA. Use a 2-tape Turing Machine. It can be done with a 1-Tape Turing Machine, but 2-tape will likely make the explanation more intuitive.

If you have a Turing machine with a tape that is not just linear at each...

If you have a Turing machine with a tape that is not just linear at each move, instead you have the ability to move up, down, left, or right. There is a single read/write head. The transition function looks like. The tape extends up and right infinitely. That is, you can never go left or down of where you start, but you can go infinitely up and to the right. Is this machine equivalent to the standard Turing machine model?...

Prove that a single-tape Turing Machine that is not allowed to write on the input portion...

Prove that a single-tape Turing Machine that is not allowed to write on the input portion of the tape can only recognize regular languages.

Find the output for the following Turing machine when run on the tape b1001b, assuming that...

Find the output for the following Turing machine when run on the tape b1001b, assuming that the machine begins in state 1 and on the left side of the tape. (1, 1, 1, 2, R) (1, 0, 0, 2, R) (1, b, 1, 2, R) (2, 0, 0, 2, R) (2, 1, 0, 1, R)

Write a java program of a multiplication table of binary numbers using a 2D array of...

Write a java program of a multiplication table of binary numbers using a 2D array of integers.

Design a Turing machine that, given a positive binary number n greater than or equal to...

Design a Turing machine that, given a positive binary number n greater than or equal to 2, subtracts 2 from this number. Test it, step-by-step, on the example of n = 2.

Given a list of numbers, could you build a Turing machine to sort them into non-decreasing...

Given a list of numbers, could you build a Turing machine to sort them into non-decreasing order? Non-decreasing order is essentially the same thing as increasing order, except that it recognizes that some of the numbers might be repeated. Explain why this is or why this is not possible. Do not try to give an algorithm or even a description of how the machine would work--just an explanation as to why it is or is not possible.

Binary Tree Create a binary search tree using the given numbers in the order they’re presented....

Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54

Short Python 3 questions a. Create a dictionary that maps the first n counting numbers to...

Short Python 3 questions a. Create a dictionary that maps the first n counting numbers to their squares. Assign the dictionary to the variable squares b. Given the list value_list, assign the number of nonduplicate values to the variable distinct_values

Subjects