Computability and Decidability

Both computability and decidability are same ,both of them talk about whether their exist a algorithm or not.

1)Algorithm is nothing but tuning machine ,but this TM is suppose to halt. Algorithm<--->TM(Halt)

but reverse is not true.Only halting tuning machine are consider as algo .

2)Halting tuning machine are subset of tuning machine and we know subset of any countable set is also countable. here we know all language are not countable and every problem can be compair to a language.Now no of problem are uncountable.As we know no of algo are countable therefore,what could be derive is that there are some problem for which algo might not be exist.

0Comment