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?

  • 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

2

http://rjlipton.wordpress.com/2009/02/24/a-conjecture-of-hartmanis/

Hartmanis' (conjectures that) if a number is easy to recognize, in a way to be made precise shortly, then it must be either rational or transcendental. It cannot be a proper algebraic number. This remains completely wide open.

The key is the notion of what it means to be “easy to recognize”. The formal notion is based on the notion of a real-time Turing Machine. A real number is computable in real-time if there is a multi-tape Turing machine that recognizes each digit in constant time. Thus, the {n^{th}} digit is recognized at time {O(n)}. Note, we insist that a stronger constraint is used: the gap between generating each digit is absolutely bounded by a constant {O(1)}.