# Can any memory-less computer operation be represented in propositional logic?

Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage.

I.e. this computer operation computes a function $f(x)=y$, without using any form of memory storage.

Q1: Is it possible for any arbitrary such $f$ to be represented by a formula $\phi(x,y)$ in propositional logic, such that $\phi(x,y) =True$ iff $f(x)=y$?

What if we relax the requirement that no temporary memory can be used?

EDIT: after reading the responses so far, perhaps it makes sense to phrase the question in the opposite way:

Q1b: What restrictions on $f(x)$ are necessary and sufficient for it to be representable in propositional logic?

• Can you give an example? Does the input $x$ have fixed length, or are you interested in integer functions such as $f(n) = n^2$? – Yuval Filmus Apr 4 '18 at 15:52
• @yuvalFilmus, the input may be a vector of words of arbitrary length from some alphabet. But the vector has to have a fixed length. I am not actually sure btw if there is a formal definition of "memory-less computation" – user56834 Apr 4 '18 at 17:14
• What do you mean by "memory?" Sometimes a mathematical function that can be physically realized by an electronic circuit or a mechanical device (e.g., something as simple as a cam and a follower) that arguably has no "memory," but a "computation" is something more than just a function. A computation typically has steps, and if a device knows what step it is working on, that's starting to sound like a kind of memory. – Solomon Slow Apr 4 '18 at 20:01
• A finite state automaton is one of the weakest devices, yet is has some "temporary storage": its finite state. Do you really want something weaker than that? What, exactly? I think it is hard to answer this question in its current state, since it is very vague on the details -- the formalization step is crucial here. – chi Apr 4 '18 at 20:20
• If some function, f, can always be computed by the same, finite number of steps, then f(x) can be computed by combinatorial logic. But that restriction--same finite number of steps--rules out many interesting functions. en.wikipedia.org/wiki/Automata_theory – Solomon Slow Apr 5 '18 at 13:43

Well you can just make a giant truth table for $f$ and then convert that to a Boolean formula. Boolean formulas are propositional formulas, are they not?

• "Well you can just make a giant truth table for $f$." I don't think this is always possible when we have an unbounded number of potential inputs. But whether this is the case isn't stated in the question. In fact, most important details aren't yet specified, so I don't think the question can be properly answered yet. – Discrete lizard Apr 4 '18 at 20:58
• If there's an unbounded number of inputs then the answer is similarly trivial. You can't because any propositional formula will only depend on a finite number of variables (inputs). But $f$ might depend on every input (e.g. the parity function). – Sebastian Oberhoff Apr 4 '18 at 21:04