0
$\begingroup$

Enumerator programs appear quite often in even an elementary computer science textbook without a formal definition. It does not seem to fit the standard definition of a computable function (through mu recursion, Turing machines or lambda calculus), which takes a single input and a single output.

What's a standard literature definition of an enumerator program? I would imagine either:

  1. A computable function that takes in an additional input i and returns the ith entry of the sequence, or

  2. A computable function f(x, y) that takes in some "state" x from the previous step, as well as some extra input y at the current step.

$\endgroup$
1
  • 2
    $\begingroup$ These are equivalent. $\endgroup$ Oct 26, 2022 at 13:54

1 Answer 1

0
$\begingroup$

One possible answer can be that an enumerater program for a set say A is actually made of two other program:

One is the program that computes A'enumerating function((a total function which its range is A)). Let's call this function f.

So it is a program that takes some natural number say m and returns f(m)

The other program is a program which is on an infinite loop and produces each natural number and gives it as input to first program.and the results are printed one after the other.

It can be helpful to consider an enumerater program as a program which takes some input ((like the on and off button)) and runs into an infinite loop and never stops.

$\endgroup$
1
  • $\begingroup$ I think the first program is sufficient. $\endgroup$ Aug 18, 2023 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.