CODEWITHSUNDEEP
algorithmproofturing-machines
E. Otero
E. Otero

Reputation: 951

The intersection of two Turing-decidable languages is Turing-decidable

Prove the intersection of two Turing-decidable languages is Turing-decidable. (Given algorithms to decide each language, describe an algorithm to determine if a string belongs to the intersection.)

I know that a language is Turing-decidable if there is an algorithm to decide membership. However, I am not sure where to start with this proof.

Any help would be much appreciated!

Upvotes: 1

Views: 4003

Answers (1)

Javier Cano
Javier Cano

Reputation: 621

First you need to define what the intersection is. It is the set of all strings that are members of both languages.

As both languages are turing decidable means that there exist such algorithm for each. You need to prove that using those algorithms you can obtain a new one that decides membership of strings in the intersection.

Hint: an algorithm that answers yes if and only if the string is in both languages.

Upvotes: 2

Related Questions