# RAM BSS model based (or its variant) computer recognizing Boolean languages

Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or its variants?(A variant could be to allow comparison. Or a RAM/BSS with weaker assumptions).

• Isn't it the case that a RAM BSS can recognize anything that an ordinary RAM machine can recognize? Simply ignore the real numbers (or, if the only values stored in RAM are real numbers, use the real numbers 0 and 1 as booleans). Jan 14, 2019 at 7:30
• by "ordinary RAM" you mean Turing machine? Jan 14, 2019 at 17:39
• No, I mean an ordinary RAM machine. Are you studying BSS real-number RAM machines without being aware of RAM machines? I recommend getting acquainted with ordinary RAM machines. Jan 14, 2019 at 17:55
• aware of RAM machines, but need to know if any languages, such as P, NP, or any other can be recognized by the RAM BSS model. Jan 14, 2019 at 17:59

Christine Gaßsner studied the question you are asking. These papers seem relevant, but you should have a look at her list of publications (DBLP):

1. The Separation of Relativized Versions of P and DNP for the Ring of the Reals. J. UCS 16(18): 2563-2568 (2010)
2. Oracles and Relativizations of the P =? NP Question for Several Structures. J. UCS 15(6): 1186-1205 (2009)
3. Relativizations of the P =? DNP Question for the BSS Model

You seem to be asking a basic question, namely: can BSS RAM machines recognize any boolean languages? Well, a BSS machine always has some kind of comparison operator, at the very least $$<$$ on real numbers. We can use it to decide equality of $$0$$ and $$1$$, from which it follows that a BSS machine can recognize at least all the languages that an ordinary RAM machine can. The more interesting question is whether it can do more than that, or perhaps more efficiently.