New answers tagged decidability
0
I have an answer to a closely related question.
Hopcroft & Ullman -79, p.170:
Theorem 7.8 $L$ is recursive if and only if $L$ is generated in canonical order
The last line of the proof reads
Note that in general we cannot exhibit a particular halting TM that accepts $L$, but the theorem merely states that one such TM exists.
It's not ...
0
This question depends on exactly what representation you use. I could imagine a few ways. The standard way would be to represent languages with machines whose languages are those we want to represent. For this context, I guess that's pretty unsatisfying. You could certainly imagine representing them with some predefined set of predicates and functions over ...
1
Sure.
There are Turing machines that always reject or always accept...
So, one of them is surely correct...
Top 50 recent answers are included
