New answers tagged computability
1
In order to show that $L_1 \leq L_2$, we need to come up with a computable function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Since $L_1 = \Sigma^*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.
In order to ...
5
If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically.
Some examples:
Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable ...
2
There is a definition, take a look at turing machines.
It still is extremely complicated to work with, so it won't be perfect. But it sill does give a different definition of computation, that can be useful in constructing theorems, such as the time hierarchy theorem.
1
Let $L=\{\langle M \rangle \mid M \text{ is a TM such }L(M)\in R\}$, where $\langle M\rangle$ is the encoding of a TM $M$, and $R$ is the set of all decidable languages. This is the language in question.
Notice that $R\neq \emptyset$ and also since there are languages not in $R$ (like the halting problem), then $R\neq RE$. Simply put, $R$ is not trivial (...
0
Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c). So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.
2
Hamkins' survey Infinite time Turing machines, linked by Yuval Filmus, formally defines a computational model (Infinite time Turing machine) that meets the requirements of a Zeno machine.
The definition of ITTMs does not use the time based framing; instead it is an extension of classical binary TMs to be defined at transfinite ordinals. A classical TM has a ...
-1
I’m not going to address the math or science, except to say it proves we can’t do a whole bunch of things and that there are even more where we can’t say they are solvable until we have solved them.
Instead I’m going to address what seems to be a common emotional reaction to the Halting Problem: that it is a cheap trick like a little boy running around ...
0
Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.
For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.
Essentially, at any ...
0
A direct diagonalization argument is very much usable here (even though a somewhat unorthodox choice, as we have "more natural" separating examples available to us).
We can construct in a straight-forward way a notation system for context-free grammars, which then lifts to a notation system $(L_w)_{w \in \Sigma^*}$ for the context-free languages. ...
3
You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.
But $\emptyset$ is not NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp ...
1
I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine.
One way to show that the language $L=\{a^p: \text{p is a prime number}\}$ is not context-free is to use pumping lemma for CFLs in the following way:
If $L$ was a CFL, then given an arbitrary long string in this language, say $...
2
Talking about suborders of $\mathbb{Q}$ explicitly makes things a bit harder to think about than is necessary, in my opinion. Really we should be talking about general computable (or rather, c.e.) linear orders - the point is that $\mathbb{Q}$ is "big enough" that we can WLOG construe these as suborders of $\mathbb{Q}$ for concreteness. This does ...
0
I can't seem to understand the logic why it is not CE, wouldn't it be CE since if it goes over 330, then we just halt?
The issue is what we do next: does halting correspond to "IN" or "OUT"?
A c.e. language is one for which we have an algorithm halting on exactly those inputs in the language. However, the "wait until you see 331, ...
Top 50 recent answers are included
