I have:

  • A programming language (P). Programs should take no input and produce a sequence of integers as output.

  • A way to enumerate all valid programs in this language (R) in a way that each program is at least as long as all programs before it.

I execute in order each entry in R. Each time I encounter output I have not seen before I add it to a set (V).

An example V:

    {}, {1}, {2}, {0, 0, 0, …},
    {1, 2, 3, …}, {2, 3, 4, …},
    {3}, {4}, {-5, -5, -5, …},
    {1, 2, 4, 8, …}

Many elements of set V will be infinite in length.

Q: Is there a function that approximates how many programs need to be run given the size of V before V increases in size by 1?

  • $\begingroup$ No. I mean, letting $f_{P, R}(n)$ be the number of programs need to be run given $n$, which is the size of $V$ before $V$ increases in size by 1, for any nonnegative computable function $g$ from $\Bbb N$ to $\Bbb N$, we can define $P$ and $R$ such that $f_{P,R}=g$. However, I doubt this is the situation you intended. $\endgroup$ – John L. Dec 25 '18 at 19:01

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.