# Tag Info

($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$, and $\le$: \begin{align*} \gcd(a,b)=c&\iff c\ge0\land c\mid a\land c\mid b\land\forall d\:(d\mid a\land d\mid b\to d\mid c)\\ &\iff c\ge0\land c\... 13 Let L_1 = L_2 = \mathbb{N} and let M \subseteq \mathbb{N} be a maximal set and let L = \mathbb{N} \setminus M be its complement. Recall that L is infinite, and that every computably enumerable (c.e.) subset S \subseteq \mathbb{N} contains either finitely many elements of L or all but finitely many elements of L. Let f : \mathbb{N} \to \mathbb{... 9 A something that might be too long for a comment, based on the previous answer by Emil. In the case you are interested in the complexity of such a logic, consider reading LICS'2015 paper by Joël Ouaknine, Antonia Lechner and Ben Worrell. A preprint is available here: https://www.cs.ox.ac.uk/people/james.worrell/LICS-main.pdf According to the authors, the ... 6 It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability >1/2, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits. Indeed, by \sigma-... 4 For a given computable f, the decidability of L_f is independent of the encoding of Turing machines if and only f is eventually injective (i.e., there exists a finite X\subseteq\def\N{\mathbb N}\N such that f\restriction(\N\smallsetminus X) is injective, or equivalently, \{\def\<#1>{\langle#1\rangle}\<n,m>:n\ne m,f(n)=f(m)\} is finite)... 3 Claim: for any function f:\{0,1\}^*\to\{0,1\}^* (not necessarily computable) and any admissible (see comments below) encoding, the language L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\}  is not decidable. Proof. Suppose, for a contradiction, that $L_f$ is decidable -- say, by a TM $M_f$. Now we construct the ...