-2
$\begingroup$

$$f:N \rightarrow B,\space B\subset N $$ and $B$ is finite, $S$ is the sequence constructed by $f(1),f(2)\cdots f(i)\cdots $. Now, if $f$ is a computable function,is $S$ eventually periodic?

Update: Secondly, if the computable function is computable in p time, is the $S$ eventually periodic? Or, under which computational complexity of the computable functions is $S$ eventually periodic?or such a computational complexity condition of computable function does not exist? Any reference is welcome.

Thirdly, what computational complexity of computable functions is the boundary under or above which the $S$ is eventually periodic or is not periodic ultimately?

Improve this question
$\endgroup$
13
  • $\begingroup$ Not necessarily. There are square-free words on three symbols which show the possibility that no repetition occurs. A simple example is the parity of the number of one's in the binary expansion of a number. Gerhard "Not Intending To Repeat Myself" Paseman, 2016.11.09. $\endgroup$
    – Gerhard Paseman
    Commented Nov 10, 2016 at 5:08
  • 1
    $\begingroup$ See here for another example (there are many): en.wikipedia.org/wiki/Fibonacci_word $\endgroup$
    – Christian Remling
    Commented Nov 10, 2016 at 5:20
  • 3
    $\begingroup$ Take two symbols a and b. the sequence a,b,a,a,b,a,a,a,b,a,a,a,a and so forth, where you repeat a with increasing multiplicity, is computable, but not periodic. $\endgroup$
    – user1688
    Commented Nov 10, 2016 at 5:50
  • 1
    $\begingroup$ This question is better suited for cs.stackexchange.com, as it is not research-level. $\endgroup$
    – Andrej Bauer
    Commented Nov 10, 2016 at 7:56
  • 1
    $\begingroup$ I think you can capture all periodic functions in linear time because you can revert it to modulo operation. On the other hand you can define constant time function that is not periodic just by printing the first digit of the input number. $\endgroup$
    – user39297
    Commented Nov 10, 2016 at 13:30

1 Answer 1

Reset to default
3
$\begingroup$

Regarding the 2nd question, the set of output sequences of an autonomous finite automaton consists of ultimately periodic sequences.

Improve this answer
$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged .