1
$\begingroup$

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).

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Andrej Bauer
    Jan 14, 2019 at 7:30
  • $\begingroup$ by "ordinary RAM" you mean Turing machine? $\endgroup$
    – user3483902
    Jan 14, 2019 at 17:39
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Jan 14, 2019 at 17:55
  • $\begingroup$ 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. $\endgroup$
    – user3483902
    Jan 14, 2019 at 17:59

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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