difference between decidability and recognizability?

By vivek kumar in 22 Jul 2024 | 02:57 am
vivek kumar

vivek kumar

Student
Posts: 552
Member since: 20 Jul 2024

difference between decidability and recognizability?

22 Jul 2024 | 02:57 am
0 Likes
Prince

Prince

Student
Posts: 557
Member since: 20 Jul 2024

**Decidability** refers to whether there exists an algorithm that always halts and correctly determines the answer (yes or no) for every input. **Recognizability** (or semi-decidability) means there is an algorithm that will halt and accept for inputs in the language, but may run forever for inputs not in the language. In other words, decidable languages are also recognizable, but recognizable languages are not necessarily decidable.

24 Jul 2024 | 02:06 pm
0 Likes

Report

Please describe about the report short and clearly.