21

($=$ 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\...


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

Let $T$ be a reasonble theory of arithmetic, say $\mathrm{PA}$. Consider the sequence $$f(m) = \begin{cases} 1 & \text{if $m$ encodes a proof of $\vdash_T 0 = 1$} \\ 0 & \text{otherwise} \end{cases} $$ The sequence is clearly computable, even primitive recursive and therefore representable in $T$. If there is $m$ such that $f(m) = 1$ then $T$ is ...


6

This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for infinitely many vectors $(a_0,\dots,a_n)\in\mathbb Z^{n+1}$, and this holds even you fix all but two of the $a_0,\dots,a_n$ in advance.


4

If you know that the $a_i$'s are all not too large, and you have a good approximation to $f(a_0,\dots,a_n)$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the details). Algorithms for finding integer relations look very closely related, and might possibly be directly applicable.


2

Using Fermat theorem, $a^p -a = 0 (\mod p) $ and if a and p are co-prime, then $ a^{p−1} − 1 =1(\mod p) $ So if u choose n to be a prime number(say p), then $a^{b^c} \mod p = a^{ (b^{c} \mod (p-1))} \mod p $ , Then you can use Fast Exponentiation trick in two levels, once for $b^c \mod p-1 $ then for $a^{b^c} \mod p $ I also suggest you to look at cses ...


Only top voted, non community-wiki answers of a minimum length are eligible