Computation Theory Let LTM be the language defined by LTM M

Computation Theory

Let LTM be the language defined by LTM M, r) I TM M loops on input I) Is this language decidable Prove your answer

Solution

Let a language be any set of strings (or words) over a given finite alphabet. The alphabet could consist of the symbols we normally use for communication, such as the ASCII characters on a keyboard, including spaces and punctuation marks. In this way any story can be regarded as a \"word\".

Definition: A language is called decidable if there exists a method - any method at all - to determine whether a given word belongs to that language or not.

Working hypothesis I: Decidability is well defined above.

The hypothesis above appears to be plausible indeed. However, considering that the concept of definability is not well defined, one might wonder whether the situation for decidability is different. Church\' thesis says that it is, and in a very profound way. But in this section I tell what can be concluded without invoking Church\' thesis, so we stick with the working hypothesis.

An algorithm or recipe for recognizing languages is anything that can be fed a word over the given alphabet, and that depending on its input either \"accepts\" the input after some time, or \"rejects\" it, or runs forever without accepting or rejecting its input. An algorithm is halting, or guaranteed to halt, if the third possibility does not occur, i.e. if it accepts or rejects within a finite amount of time. Any method that qualifies for the definition of decidability above counts as a halting algorithm for recognizing languages.

Proposition: The decidable languages are closed under union and intersection.

Proof: Let L and M be languages that are decided by algorithms A and B respectively. In order to decide their union (or intersection) simply run A and B in parallel on the same given input string until they either accept or reject. The input string is accepted iff either one (or both, respectively) accepts it, and rejected otherwise.

Proposition: The decidable languages are closed under complementation.

Proof: Upon halting, simply exchange the verdicts accept and reject.

Yes it is.