The Gateway to Computer Science Excellence
+1 vote

I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of states? 

in Theory of Computation by Active (4.5k points) | 99 views

1 Answer

+2 votes
We can make every recursively enumerable language to follow this property by doing a little modification which is that we can add a useless state in case of TM with odd no of states due to which they will also have an even number of states. Hence for each of the recursively enumerable languages, we can have TM correspond to them having an even number of states thereby making it a trivial property.
by Active (3.3k points)

Related questions

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
50,737 questions
57,385 answers
105,370 users