I'm currently learning some things about BSS RAMs. For sake of simplicity, please imagine them as a Turing machine over the reals.
Now, this machine gets some real numbers as input. The input values form nearly a string, but are not of finite length as decimal representation. Additionally, there are infinitely many real numbers.

A language on the other hand is often defined as being a subset of Kleene's Hull over a finite (!) alphabet.

Is it valid and reasonable to define languages over an infinite alphabet to represent the input set of a BSS RAM?

  • $\begingroup$ BSS machines typically compute functions rather than decision problems. $\endgroup$ Dec 14 '18 at 22:57
  • $\begingroup$ If you arrange for the machine to output a 0,1 value, then you can think of it as a subset of $\mathbb{R}^n$ for some $n$. Since the number $n$ is fixed, it doesn't really make much sense to consider the input as a word, which typically has arbitrary (finite) length. $\endgroup$ Dec 14 '18 at 22:59
  • $\begingroup$ I am aware of the difference between functions and decision problems and do not know where in my question I shall have interchanged these terms. $\endgroup$ Dec 14 '18 at 23:30
  • $\begingroup$ IMHO, the second comment is false. The BSS-RAM following my definition (after C. Gaßner) gets an input out of $\mathbb{R}^{\infty}$ (tuples of arbitrary length). (I never consider the infinite case with input set $\mathbb{R}^{\mathbb{N}}$.) The input length in the finite case is given by the first index register's content. and thus not of fixed length. $\endgroup$ Dec 14 '18 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.