Question

1. What is a Turing Machine? Be able to describe its parts.
2. Given a Turing Machine description, be able to carry out a computation and show the resultant tape.
3. What is the halting problem?
4. Is the halting problem decidable?
5. What is Hoare Logic?
6. When proving a program correct, we must look at the initial assertion and final assertion. What are these?
7. What is a loop invariant?

Answer 1

1.What is a Turing Machine? Be able to describe its parts.

A Turing machine are often thought of as a finite state machine sitting on an infinitely long tape containing symbols from some finite alphabet Σ. Based on the symbol it’s currently reading, and its current state, the Turing machine writes a replacement symbol therein location (possibly an equivalent because the previous one), moves left or right or stays in place, and enters a new state. It may also plan to halt and, optionally, to output “yes” or “no” upon halting.

Parts of Turing machine:

1. A tape, infinite in both direction, divided into equal-sized cells, contains symbols from the alphabet ;

the tape may contain only finitely many characters different from and they should be consecutive;

2. a register, containing values from, which determines the actual behavior of the Turing machine;

3. a read-write head, pointing always to a specific cell, this connects a tape and therefore the register.

{ Note: 2nd Question is going to be a very long answer, solving 2nd one and others is not possible, sorry for inconvenience}

3.What is the halting problem?

Given a program or algorithm will ever halt or not?
It means the program on specific input will accept it and halt or reject it and halt and it'd never enter an infinite loop. Basically halting means terminating. So can we've an algorithm which will tell that the given program will halt or not? In terms of the Turing machine , will it terminate when run on some machine with some particularly given input string?

The answer is "NO" we can't design a generalized algorithm which will appropriately say that given a program will ever halt or not?
The only way is to run the program and check whether it halts or not.
We can refrain the halting problem question in such how also: Given a program written in some programming language will it ever get into an infinite loop(loop never stops) or will it always terminate(halt)?

4.Is the halting problem decidable?

This is an un-decidable problem because we cannot have an algorithm which will tell us whether a given program will halt or not during a generalized way i.e by having a selected program/algorithm. generally , we can’t always know that’s why we can’t have a general algorithm. the simplest possible way is to run the program and see whether it halts or not. during this way, for several programs, we will see that it'll sometimes loop and always halt.

5.What is Hoare Logic?

Hoare logic (also referred to as Floyd–Hoare logic or Hoare rules) is a formalism with a group of logical rules for reasoning rigorously about the correctness of computer programs. it had been proposed in 1969 by British scientist and logician Tony Hoare and subsequently refined by Hoare and other researchers.