New answers tagged

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