New answers tagged

4

Let $L$ be the set of powers of 2 encoded in base 3. The encoding of $4^n$ in base 3 ends with 1, whereas the encoding of $2\cdot 4^n$ in base 3 ends with 2. Hence $L' = L \cap \Sigma^*1$ is the encoding of all powers of 4. The encoding of an integer $m > 0$ in base 3 takes $\lceil \log_3 (m+1) \rceil$ digits. Since neither $4^n$ nor $4^n+1$ are powers ...


4

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$. Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$. (If $A$ is a set of strings then we first turn it onto a [i.e. replace it by a Turing equivalent] set of integers or equivalently an infinite binary sequence ...


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...


3

As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space". However, this should not prevent us from giving precise definitions of "model of computation". As our understanding and motivations change, so will the definitions. And keep ...


4

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words ...


-3

https://www.staff.science.uu.nl/~ooste110/talks/NMC53.pdf this reference says MoC’s are structured in a category (in fact, a 2-category).


Top 50 recent answers are included