Awesome q2a theme
+1 vote
53 views
As per the definition of a Turing Machine, it does not accept Epsilon. But, A →  ϵ  can be generated by a Unrestricted Grammar. So, how can we say that Turing Machines are the acceptors for Recursively Enumerable languages generated by Unrestricted Grammar?
in Theory of Computation by (9 points) | 53 views
0
There exists a Turing machine that accepts $\epsilon$. You are probably confusing it with a decider.
0

it does not accept Epsilon

Citation needed.

There very much exist TM's that recognize $\epsilon$. Trivial example would be one that has a transition $q_{initial}, B, B, R/L, q_{final}$

If you cannot digest that because it is too trivial - you can also build a machine that upon reading $\epsilon$, performs a prime factorization of some unique large number while going through a hundred different states and then accepts. Net result would still recognizing $\epsilon$.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,998 questions
3,130 answers
14,378 comments
95,816 users