Ultratasks in the ITTM Model

Question

[Note: I have not previously seen a definition that relates Beth numbers to Supertasks, however my intuition is that one may exist]

A supertask is a countably infinite sequence of operations that occur sequentially within a finite interval of time

JDH has written a paper on ITTMs & Supertasks (Infinite Time Turing Machines: Supertask Computation)

To define the beth numbers, start by letting $\beth _{0}=\aleph _{0}$ be the cardinality of any countably infinite set.

I think $\beth_0$ would correlate to the first supertask (&/or the first ITTM).

Supertasks are called "hypertasks" when the number of operations becomes uncountably infinite.

Is there a good notion of hypercomputation which allows inaccessible-length computations?

$\beth _{\omega }$ (pronounced beth omega) is the smallest uncountable strong limit cardinal.

Again, I think $\beth_{\omega}$ would correlate to the first hypertask (&/or $\Sigma$?)

A hypertask that includes one operation for each ordinal number is called an "ultratask".

Here, I am at a loss. To start with, I'm not entirely sure how to mathematically show one operation for each ordinal in addition to the uncountably infinite operations of the hypertask (in any notation; my best guess in beth notation is $\beth_{\omega}+\beth_0$). Additionally, I'm unsure how/if ultratasks could be modeled w/ ITTMs.

Questions

• Can hypertaks & ultratasks be modeled with ITTMs?
• What are the cardinalities of supertasks, hypertasks & ultratasks?

Answer 1

The question has a lot of individual claims and questions. I'll try to address most of them, but not in the order in the OP.

For convenience, I'll assume $\mathsf{ZFC}$ throughout.

2. What are the cardinalities of supertasks, hypertasks & ultratasks?

The first paragraph of the Wikipedia article on supertasks which you quoted without citing answers this fairly explicitly:

• "a supertask is a countably infinite sequence of operations" So supertasks correspond to cardinality $\aleph_0=\beth_0$.
• "Supertasks are called 'hypertasks' when the number of operations becomes uncountably infinite." So any other infinite cardinality would correspond to a hypertask.
• "A hypertask that includes one operation for each ordinal number is called an 'ultratask'." Since the ordinals don't fit in a set, no cardinality (beth number or otherwise) would suffice.

0. Set Theory misconceptions

each ordinal in addition to the uncountably infinite operations

The collection of ordinals is so large they don't fit in a set, and the ordinals below any uncountable one already form an uncountably infinite set. There's no "in addition" at play here.

My best guess in beth notation is $\beth_\omega+\beth_0$.

This appears to involve a blind guess at what cardinal addition might mean. The definition can be looked up on Wikipedia instead of guessing. In particular, $\beth_\omega+\beth_0=\beth_\omega$.

I think $\beth_\omega$ would correlate to...

As far as I can tell, you are making another blind guess, and conflating all (or at least some pairs) of the following:

• "smallest uncountable cardinal" (which would be $\aleph_1$, the smallest cardinality for the operations of a hypertask)
• "smallest uncountable strong limit cardinal" ($\beth_\omega$)
• "(strongly) inaccessible" (as you linked that other question about hypercomputation)
• "non-admissible ordinal", or some other thing that made you think of $\Sigma$. Very importantly, $\Sigma$ is a particular countable ordinal, not a cardinal like $\beth_0$ (its cardinality) or $\beth_\omega$ (a larger cardinal).

If you would like to learn about all of these concepts, I would recommend starting with an undergrad text on set theory, and then graduate text(s) on set theory and logic for the "admissible" stuff.

1. Can hypertasks & ultratasks be modeled with ITTMs?

Technically yes, but only extremely boring ones, so not really.

From the paper on ITTMs you linked:

We extend the computation into transfinite ordinal time by simply specifying the behavior of the machine at the limit ordinal stages

There is no restriction there on which limit ordinal stages could be handled, so an ultratask going through all of them is conceivable.

However:

The fact is that every [ITTM] computation either halts or repeats in countably many steps.

Because of this, the hyper/ultratasks that an ITTM does are nothing new on top of the supertasks.

[Would $\beth_0$] correlate to the first supertask (&/or the first ITTM)[?]

Not really. You count steps with ordinals (like $\omega$), not cardinals. Given the above, in some sense every computation on an ITTM (that doesn't halt in finite time) would correlate with $\beth_0$.

...a definition that relates Beth numbers to Supertasks...

• Given the strict definition of "supertask" as a countably infinite sequence, then as mentioned above, the only relevant Beth number is $\beth_0$.
• Given, instead, a broader definition encompassing hypertasks as well, then hypertasks may have cardinalities of the set of operations equal to any Beth number:
  • If GCH is true, then those are the only cardinalities of hypertasks (assuming a set of operations, unlike an ultratask).
  • But if GCH is false, then there are tons of other cardinalities that a hypertask could have.