Problem 3 Say that a language L 21, 2,...) is enumerable if there exists a two-t
ID: 662291 • Letter: P
Question
Problem 3 Say that a language L 21, 2,...) is enumerable if there exists a two-tape TM M that outputs r 2 a3 on a designated output tape. The other tape is a designated work tape. The output 1 tape is write-only, with the head moving only from left-to-right. Say that L is enumerable in lericographic order if Lis enumerable as above but where, additionally, r1 2 z3 where denotes the lexicographic order. 3.1. Prove: L is r.e. iff it is enumerable 3.2. Prove: L is recursive iff it is enumerable in lexicographic orderExplanation / Answer
3.1
Consider, L to be enumerable language.
Given, language is said to be enumerable when there exists a two-tape Turing Machine M that outputs on a designated output tape. The other tape is a designated work tape.
Thus, there exists a Turing machine M for enumerable language.
A language is said to be recursively enumerable if there exists a Turing Machine that enumerate all valid strings of the language. The strings should contain the alphabets which are accepted over the input tape.
Thus, for a language to be recursively enumerable it should compulsorily be an enumerable language. This is because, enumerable language defines the existence of Turing machine and recursively enumerable language defines the acceptance of strings over a Turing machine.
3.2
Assume that a language L is enumerable in lexicographic order.
A language is said to be in lexicographic order if L is enumerable and the input alphabets are executed in lexicographical order. Such as .
There also exists a Turing machine for a string which is not present in lexicographical order. The string is also an acceptable string over the Turing machine M and does not follow Lexicographical order. The string is a recursive language.
This is a contradiction to our assumption.
Thus, for a language to be recursive it need not to be enumerable in lexicographical order.
Thus, the statement can be concluded as a language L is decidable iff it is enumerable in lexicographic order.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.