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?

  • $\begingroup$ 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$? $\endgroup$ Apr 4, 2018 at 15:52
  • $\begingroup$ @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" $\endgroup$
    – user56834
    Apr 4, 2018 at 17:14
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 4, 2018 at 20:01
  • 3
    $\begingroup$ 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. $\endgroup$
    – chi
    Apr 4, 2018 at 20:20
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 5, 2018 at 13:43

2 Answers 2


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?

  • $\begingroup$ "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. $\endgroup$
    – Discrete lizard
    Apr 4, 2018 at 20:58
  • $\begingroup$ 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). $\endgroup$ Apr 4, 2018 at 21:04

You asked about "computer operation".

One of the three RSAs (Rivest, Shamir, Adleman, can't remember which one) proposed a chip that would be able to find prime factors of 1024 bit integers in quite a reasonable time (feed in the number at one end of the chip, wait a few minutes, and a factor comes out at the other hand), at a proposed cost of about $50 million, a few years ago. Can't remember the exact time, but it was so enormous that there must be some kinds of loops involved. "Proposed" means that he actually figured out in detail how it would work.

(Memory coming back: Not one chip. Not one wafer worth of chips. Many, many wafers).

Whether you say there is "memory" or not is up for debate, but I'm quite sure that you can't replicate the operation of this chip with propositonal logic. Of course the whole problem, being fixed size, can be solved with propositional logic, but most likely of a size that any attempt to write it down would exceed the size of the universe.

  • $\begingroup$ Indeed, I don't mean that it is practically doable, but theoretically doable. so if it exceeds the size of the universe, that is fine. $\endgroup$
    – user56834
    May 12, 2018 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.