• DocumentCode
    707618
  • Title

    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

  • Author

    Sharma, Chetan ; Shakya, Rinku

  • Author_Institution
    Dept. of Comput. Sci. & Eng., Chitkara Univ., Rajpura, India
  • fYear
    2015
  • fDate
    11-13 March 2015
  • Firstpage
    2091
  • Lastpage
    2096
  • Abstract
    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.
  • Keywords
    Turing machines; computational complexity; context-free languages; context-sensitive languages; Chomsky hierarchy; computational complexity; computer memory; context free language; context sensitive language; deterministic turing machine; electronic computers; general-purpose computers; halting theory problem; language string processing; regular language; Computers; Context; Grammar; Magnetic heads; Time complexity; Turing machines; Chomsky hierarchy; context free; context sensitive; halting state; universal;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing for Sustainable Global Development (INDIACom), 2015 2nd International Conference on
  • Conference_Location
    New Delhi
  • Print_ISBN
    978-9-3805-4415-1
  • Type

    conf

  • Filename
    7100608