1
$\begingroup$

I am reading historical stuff on the algebraic and transcendental numbers. Descartes, in his Geometry, excluded all curves not expressible as algebraic equations. Later, Leibniz called such curves transcendental.

I wonder now which automata recognise exactly the algebraic numbers? As Turing showed, Turing machines can recognise all algebraic numbers. Apparently, finite state machines cannot recognise algebraic numbers. So, there must be an automata class between that does the job?

  • 3
    Among what numbers? What kind of input are you using?2012-05-21
  • 0
    The computable numbers are the real numbers computable by a Turing machine. So I am looking for something like "The algebraic numbers are the real numbers computable by ...". Basically, anything on the relation of algebraic numbers and automata would be of interest to me.2012-05-21
  • 1
    @corto: Qiaochu probably means to ask how you code your inputs. A Turing machine, by definition, only accepts finite-length inputs so it cannot accept, say, the decimal representation of a real number as an input. If you are thinking of chaining Turing machines together then that won't work – Rice's theorem tells us that there can be no decision procedure for properties of _outputs_ of Turing machines.2012-05-21
  • 0
    @corto: _a priori_ one must distinguish between "computable by" and "recognizable by." One is about outputs and one is about inputs.2012-05-21
  • 0
    I go for both..;) I would be just interested in any kind of information on the relation between algebraic numbers and automata theory. Can the algebraic numbers somehow be characterised by some automata class? If the question is trivial or too vague I would also be happy with some textbook.. It is just the case that I cannot find anything on this anywhere..2012-05-21
  • 0
    Ok, this probably sheds more light on my question http://cstheory.stackexchange.com/questions/10495/decidability-of-transcendental-numbers2012-05-21

1 Answers 1