{"id":6559,"date":"2026-03-19T10:29:43","date_gmt":"2026-03-19T04:59:43","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6559"},"modified":"2026-03-30T17:17:50","modified_gmt":"2026-03-30T11:47:50","slug":"turing-machine","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/turing-machine","title":{"rendered":"Turing Machine"},"content":{"rendered":"<h2 style=\"text-align: center;\">What is Turing Machine in TOC?<\/h2>\n<p style=\"text-align: justify;\">Turing Machine recognizes the recursive enumerable language. Turing Machine is more powerful than any other automata such as finite automata, PDA and LBA. TM accepts recursive enumerable language by using universal acceptance mechanism Turing Machine enumerates the recursive enumerable language.<\/p>\n<p style=\"text-align: justify;\">Turing Machine computes the partial recursive function. Turing Machine can be modeled as Deterministic Turing Machine (DTM) or Non-deterministic Turing Machine (NTM). By default, a Turing Machine is a DTM. The power of DTM and NTM is the same.<\/p>\n<p style=\"text-align: justify;\"><strong>1. Turing Machine Acts as Recognizer or Acceptor:<\/strong> Turing Machine that accepts or recognizes the<br \/>\nstrings of a recursive enumerable language (L) over an input alphabet \u2211.<\/p>\n<p style=\"text-align: justify;\"><strong>2. Turing Machine Acts as enumerator:<\/strong> Turing Machine enumerates the string of recursive enumerable language over the input alphabet \u2211.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-6561 size-full aligncenter\" src=\"https:\/\/study.madeeasy.in\/wp-content\/uploads\/2026\/02\/Turing-Machine.jpg\" alt=\"Turing Machine \" width=\"477\" height=\"432\" srcset=\"https:\/\/www.madeeasy.in\/study\/wp-content\/uploads\/2026\/02\/Turing-Machine.jpg 477w, https:\/\/www.madeeasy.in\/study\/wp-content\/uploads\/2026\/02\/Turing-Machine-300x272.jpg 300w\" sizes=\"auto, (max-width: 477px) 100vw, 477px\" \/><\/p>\n<h2>Specification of Turing Machine<\/h2>\n<p><strong>The Turing machine is represented as a seven tuple as follows:<\/strong><\/p>\n<p>TM = (Q, \u03a3, \u0393, \u03b4, q0, B, F)<\/p>\n<p>where Q = set of finite states, \u03a3 = input alphabet (\u03a3 \u2286 \u0393), \u0393 = tape alphabet, and \u03b4 =\u00a0transition function;<\/p>\n<p><strong>DTM \u03b4 :<\/strong> Q \u00d7 \u0393\u2192 Q \u00d7 \u0393 \u00d7 {L, R}<br \/>\n<strong>NTM \u03b4 :<\/strong> Q \u00d7 \u0393\u2192 2Q \u00d7 \u0393 \u00d7 {L, R}<\/p>\n<p>B= blank symbol (B \u2208 \u0393)<br \/>\nF= final states (F \u2286 Q)<\/p>\n<ul>\n<li>The argument of \u03b4 are<br \/>\nAs for DTM \u03b4 : Q \u00d7 \u0393\u2192 Q \u00d7 \u0393 \u00d7 {L, R}<br \/>\n\u201cThe current state of the control unit and the current tape symbol being read (i.e. Q \u00d7 \u0393). The result is a new state of the control unit, a new tape symbol, which replaces the old one and a move symbol, L or R (i.e. Q \u00d7 \u0393 \u00d7 { L, R}). The move symbol indicates whether the read-write head moves left or right one cell after the new symbol has been written on the tape\u201d.<\/li>\n<li>Both non deterministic Turing machine or deterministic Turing machine have same power and they<br \/>\nare interconvertible.<\/li>\n<li>No logical machine can have more power than Turing machine.<\/li>\n<\/ul>\n<p style=\"text-align: center;\"><a class=\"btn btn-danger\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/greibach-normal-form-gnf\" target=\"_blank\" rel=\"noopener\">&lt;&lt; Previous<\/a> | <a class=\"btn btn-success\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/finite-automata\" target=\"_blank\" rel=\"noopener\"> Next &gt;&gt;<\/a><br \/>\n<strong> Must Read: <\/strong> <a href=\"https:\/\/study.madeeasy.in\/cs-it\/what-is-theory-of-computation\" target=\"_blank\" rel=\"noopener\"><strong>What is Theory of Computation?<\/strong><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>What is Turing Machine in TOC? Turing Machine recognizes the recursive enumerable language. Turing Machine is more powerful than any<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,1930],"tags":[1945,1947,1946],"class_list":["post-6559","post","type-post","status-publish","format-standard","hentry","category-cs-it","category-computation","tag-turing-machine","tag-turing-machine-acts-as-enumerator","tag-turing-machine-acts-as-recognizer-or-acceptor"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6559","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6559"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6559\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6559"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6559"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6559"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}