Assignment-1

1. Define what a Turing machine is.

   • Turing machine is the abstract model of all computers.
   • A Turing machine consists of a tape divided into cells, a moving read/write head, a state register storing the state of the Turing machine.
2. What is a UTM?

   • UTM is a Turing machine that could simulate all other Turing machines.

1. Describe the seven levels of transformations of a computer system.

• The seven levels of transformations in a computer system represent the progression from identifying a problem to the physical realization in a device. It starts with understanding the problem and formulating an algorithm, then translating it into a program. The program is mapped to an instruction set architecture, which is further implemented in a microarchitecture. At a lower level, the microarchitecture is translated into circuits, and finally, these circuits are realized in physical devices.

1. Explain the fetch-decode-execute cycle of the von Neumann Architecture.

   • the control unit fetch the next instruction from the memory
   • the instruction is decoded into a language that the ALU understands
   • data operands are fetched from the memory into the registers inside CPU
   • the ALU executes the instruction and places the result into the registers or memory

1. Given 8 bits, represent the numbers +53 and -109 into binary using the following approach: 1) Signed-magnitude; 2) One’s complement; 3) Two’s complement.

• +53:
  1. Signed-magnitude: 00110101
  2. One’s complement: 00110101
  3. Two’s complement: 00110101
• -109
  1. Signed-magnitude: 11101101
  2. One’s complement: 10010010
  3. Two’s complement: 10010011

1. Convert -57.625 into binary using 32 bits floating number representation. Show your steps.

• -57.625 in binary using 32 bits floating number representation:
  • 1100 0010 0110 0110 1000 0000 0000 0000

• Consider two hexadecimal numbers: x434F4D50 and x55544552. What values do they represent for each of the five data types shown?

• The following Turing Machine is supposed to count in base 2. Fill in the missing rules.

{
   "name": "Binary Increment",
   "max_state": 25,
   "symbols": "xyzabc01$@",
   "tape": "100",
   "position": 2,
   "rules": [
      [ 0, "#", "1", 1, "R" ],
      [ 0, "0", "1", 1, "R" ],
      [ 0, "1", "0", 0, "L" ],
      [ 1, "#", "#", 0, "L" ],
      [ 1, "0", "0", 1, "R" ],
      [ 1, "1", "1", 1, "R" ]
   ]
}
Copy

• Show that

• 1. Using truth table; (5 points)

• 2. Using Boolean identities; (5 points)

a. Write the Boolean expression in sum-of-products form.

b. Write the Boolean expression in product-of-sums form.

c. Simplify the sum-of-products form using Boolean identities;

d. Draw the logical circuit diagram for the simplified Boolean expression;

• Simplify the above Boolean expression using K-MAP.