New answers tagged computability
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 ...
4
Internal parametricity does not entail any version of extended Church's thesis. To see this, consider a presheaf model of internal parametricity, for example this one, and observe that in any presheaf model of type theory the extended Church's thesis fails (both the internal and the external one) because the object $\mathbb{N}^\mathbb{N}$ has uncountably ...
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
