0
\$\begingroup\$

An infinite time Turing machine is a generalization of a Turing machine to infinite computation lengths. It has three tapes: two of them are blank initially, and the other one contains the input to the machine.

This challenge is similar, yet no programming language has been known to simulate an ITTM. As such, the goal is instead to submit a function \$f: \mathbb{N} \rightarrow \mathbb{N} \cup {\textrm{HALT}}\$ (where HALT is some distinguishable value outside \$\mathbb{N}\$). Then, define \$n_0 = 0\$, \$n_{\alpha+1} = f(n_\alpha)\$ (if \$n_\alpha \neq \textrm{HALT}\$), and if α is a limit, \$n_α\$ is the bitwise limit superior of \$n_\beta\$ for \$\beta < \alpha\$ (if all \$n_\beta \neq \textrm{HALT}\$).

Rules

  • If \$f(\alpha) \in \mathbb{N}\$ for all \$\alpha < \beta\$, then the bitwise limit superior of such values should also be in \$\mathbb{N}\$.

  • Your score is \$(V, B)\$, where \$B\$ is how many bytes your program is, and \$V\$ is the ordinal with \$n_\alpha = \textrm{HALT}\$.

  • To compare scores we define a partial order \$\leq\$ so that \$(v_0, b_0) \leq (v_1, b_1)\$ iff \$v_0 \leq v_1\$ and \$b0\geq b1\$. A score \$(v_0,b_0)\$ is better than a score \$(v_1,b_1)\$ iff \$(v_0, b_0) \leq (v_1, b_1)\$ and they are not equal.

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ This can be an interesting challenge. It's very similar to a challenge I have in the sandbox. But there are some issues here in that a lot of things are not very well defined. The most gaping hole would be what it means to "simulate" an ITTM in this context. I would suggest sandboxing this sort of question first. \$\endgroup\$
    – Wheat Wizard ♦
    Jan 26 at 18:35
  • 1
    \$\begingroup\$ I don’t think anyone has built a programming language that simulates an ITTM. I would suggest leaving Turing machines out of the question entirely. Submit a function \$f: \mathbb N → \mathbb N ∪ \{\mathtt{HALT}\}\$ (where \$\mathtt{HALT}\$ is some distinguishable value outside \$\mathbb N\$). Define \$n_0 = 0\$, \$n_{α + 1} = f(n_α)\$ (if \$n_α ≠ \mathtt{HALT}\$), and if \$α\$ is a limit, \$n_α\$ is the bitwise lim-sup of \$n_β\$ for \$β < α\$ (if all \$n_β ≠ \mathtt{HALT}\$). Your score is \$(α, \textrm{bytes})\$ where \$α\$ is the ordinal with \$n_α = \mathtt{HALT}\$. \$\endgroup\$
    – Anders Kaseorg
    Jan 26 at 22:28
  • \$\begingroup\$ Also, I would suggest stealing the Pareto-frontier scoring system from this challenge. \$\endgroup\$
    – Anders Kaseorg
    Jan 26 at 22:31
  • \$\begingroup\$ @AndersKaseorg The bitwise limsup of \$n\in\mathbb{N}\$ is not always within \$\mathbb{N}\$. You probably would need to replace \$\mathbb{N}\$ with an actual tape type or at least something that is closed under \$\mathrm{limsup}\$. \$\endgroup\$
    – Wheat Wizard ♦
    Jan 26 at 22:35
  • \$\begingroup\$ Or you could require that \$f\$ be written such that the bitwise lim-sup remains within \$\mathbb N\$. \$\endgroup\$
    – Anders Kaseorg
    Jan 26 at 22:41

0

Reset to default

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.