Question

5. Formulate the Halting Problem for Turing machines and state its fundamental property In one-two senetences (not more) explain what it means for the problem of automatd software verification?

Answer 1

Answer is as follows:

a)

In the computation the Halting Problem is the problem of finding, description of any computer program and an input. It state wheater the program will run completly or continue to run forever.Halting is undecidable problem.

It tells about the properties of computer program that are fixed in turing model of computation.

Prooperty :

It is the set of objects possessing the property in question. The halting set

K := { (i, x) | program i halts when run on input x}

represents the halting problem.

This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains

b)

In automated software verification the haltig problem tell about the program termination on input.

According to this, Any non-trivial property of partial functions, there is no general and effective method to decide if program computes a partial function with that property.

if there is any query please ask in comments...