Computational complexity in language string processing and theory of halting problem in deterministic turing machine accepting context sensitive language, context free language or regular language

摘要

Turing machines are equivalent to modern electronic computers at a certain theoretical level, but differ in many details. In the analogy with a computer, the “tape” of the Turing machine is the computer memory, idealized to extend infinitely in each direction. The remarkable fact is that certain Turing machines are “universal”, in the sense that with appropriate input, they can be made to perform any ordinary computation. Not every Turing machine has this property; many can only behave in very simple ways. In effect, they can only do specific computations; they cannot act as “general-purpose computers”. Turing machine can process different types of strung written in various type language defined by Chomsky hierarchy. Machine will stop when it didn't have proper input or a machine state which is stable but not final and show halting state of machine. In this paper we are trying to describe using a example that a Turing machine can accept a language or string defined by context sensitive, context free or regular language till it find suitable input, but it show the halting state of the machine when it does not reach to a state closure to the final state along with the complexity of the process to process of that language or string.