Turing Machine

Question

State True or False and why?

1)Any language computable by TM must be Recursive

2) If we replace the word "computable" with "accepted" does the question gives same meaning?

Answer 1

1) True

2) No , Now it's RE language.

REC=Turing Computable

When we say some function f(x) is computable then we basically means that there exists an algorithm to do the computation of that function. And when there exists an algorithm then we have answer for YES as well as NO(for member and non-member of language)and in that way the language becomes REC(recursive).

RE=Turing Acceptable=Semi Decidable=Turing Recognizable=Turing Enumerable

If some language is accepted by Turing machine then

Members of the language will halt in final state and Non-members may halt in non-final state or hang.

Comments

U mean turing computable means turing decidable

and turing acceptable means turing undecidable

---

Turing acceptable means Turing undecidable ;- false statement.
Turing acceptable means RE language which is semi decidable problem.
A semi decidable problem whose complement is not semi decidable is undecidable problem.
If complement of semi decidable problem is semi decidable too then problem becomes decidable.
Undecidable = RE which is not REC.
Semi decidable can be decidable or undecidable.