EDB — 04B

Exercises

1. [04B]Consider the set ${\mathbb{N}}^{\mathbb{N}}$ of functions $f:\mathbb{N}\to \mathbb{N}$; and the subset $\mathcal{A}$ of $f$ of functions that can be defined using an algorithm, written in a programming language of your choice (also assuming that the computer that is running this algorithm has potentially unlimited memory) and such that for each choice $n\in \mathbb{N}$ in input the algorithm must finish and return $f(n)$. Compare the cardinalities of ${\mathbb{N}}^{\mathbb{N}}$ and $\mathcal{A}$.

   [ [04C]↺↻]