capbtabboxtable[][] [a]M. A. Clark

# Maximizing the Bang Per Bit

Dean Howarth  Jiqun Tu  Mathias Wagner  Evan Weinberg

###### Abstract

Reducing memory traffic is critical to accelerate Lattice QCD computations on
modern processors, given that such computations are memory-bandwidth bound. A
commonly used strategy is mixed-precision solvers, however, these require
careful treatment to ensure stable convergence. We give an overview of the
strategies employed in QUDA to stabilize mixed-precision variants of Conjugate
Gradient (CG), and its multi-shift brethren. Through the use of customized
numerical storage formats we can significantly improve upon the precision
achievable compared to IEEE numerical formats, increasing both the solver
precision and stability achievable at fixed word size. We give examples using
BiCGStab($l$) and multi-shift CG solvers using the HISQ operator.

##  1 Introduction

It is well known that lattice quantum chromodynamics (LQCD) calculations are
memory bandwidth bound on modern computing architectures, this stemming from
the low arithmetic intensity of the discretized fermion operators (stencils)
which are the computational dominant kernel in most LQCD computations. Given
that the expected future trajectory of computer architecture will exacerbate
the gap between computational throughput and memory bandwidth, we cannot
expect future supercomputers to remedy this situation.

In order to soften this bottleneck there have been a number of techniques
deployed, both as part of general HPC developments, and in a domain-specific
approaches specifically for LQCD computations.

  * •

Cache blocking: the number of redundant loads can be minimized by utilizing a
cache tiling-strategy, where temporal locality is exorcised to reuse loads in
on-chip cache [1, 2].

  * •

Block solvers: by deploying a batched linear solver, where multiple right hand
sides are solved simultaneously, the memory traffic to load the stencil
coefficients can be amortized. This transformation effectively turns a matrix-
vector problem, into a matrix-matrix problem, increasing the arithmetic
intensity as a result [3].

  * •

Compression: LQCD is a theory that is blessed with many symmetries that can be
harnessed to reduce their memory footprint. In particular, the link-field
matrices that appear in the Dirac stencil are, depending on the smearing used,
usually a member of the SU(3) group. This allows one to reduce the real
numbers required to exactly store each matrix from 18 to 12 or as few as eight
real numbers [4, 5].

  * •

Mixed-precision Krylov solvers: using less precision to store fields means
less time spent loading / storing those field. The most commonly used approach
is to use “double-single” solvers, where the bulk of the work is done using
IEEE 754 single precision, FP32, with correction to IEEE 754 double precision,
FP64, though “double-half” is also deployed, particularly in the QUDA library
(see $\S\ref{sec:ieee}$).

In this work we focus on a new approach to tackle the memory bandwidth crunch:
how to improve precision at a fixed number of bits. In doing so we ask
ourselves, what would the optimum numerical format be for an LQCD-type
problem? Almost all modern microprocessors that are capable of floating point
adopt the IEEE 754 convention, however there is no reason why the IEEE formats
are the optimum ones for LQCD data.

The fact that we are constrained to using IEEE floating point for the actual
computation is not an issue since we are free to decouple the computation
format from the storage format, with the expectation that any custom format
would only be used for storage and we would convert to IEEE format for the
computation. Thus our Achilles heal of being bandwidth limited becomes a great
advantage: it provides us a computational budget to deal with potentially
expensive unpacking and packing at the beginning and end of any computation,
respectively.

This paper is broken up as follows: in §2 we describe the IEEE numerical
formats and briefly introduce the pre-existing QUDA half-precision format that
was a precursor to this work. In $\S\ref{sec:solvers}$ we describe the
stabilized mixed-precision CG and multi-shift CG solvers that QUDA utilizes,
that have not been described in the literature prior. Our alternative
numerical formats are described in §4, and we describe the approach to
implementing these formats in $\S\ref{sec:implementation}$, as well as testing
the efficacy of our approach. In $\S\ref{sec:solver_results}$ we present
initial solver results using these numerical formats. Finally in §7 we
summarize our findings, and we propose future research directions and
applications of our technique. In this work we present using HISQ staggered
fermions, however, there is nothing tied to the discretization employed, and
our methods are equally applicable to Wilson fermions, etc.

##  2 IEEE and QUDA numerical formats

The IEEE floating point formats [6] are partitioned into a sign bit, mantissa,
and exponent, with the mantissa bits defining the precision of the
representation, and the exponent bits setting the possible range. In Table 1
we summarize the IEEE primary floating point formats.

| exponent | mantissa | epsilon | smallest | largest
---|---|---|---|---|---
| width | width |  | number | number
half | 5 | 10 | $2^{-11}\sim 4.88\times 10^{-4}$ | $\sim 6.10\times 10^{-5}$ | 65504
single | 8 | 23 | $2^{-24}\sim 5.96\times 10^{-8}$ | $\sim 1.18\times 10^{-38}$ | $\sim 3.40\times 10^{38}$
double | 11 | 52 | $2^{-53}\sim 1.11\times 10^{-16}$ | $\sim 2.23\times 10^{-308}$ | $\sim 1.80\times 10^{308}$
quad | 15 | 112 | $2^{-113}\sim 9.63\times 10^{-35}$ | $\sim 3.36\times 10^{-4932}$ | $\sim 1.19\times 10^{4932}$
Table 1: IEEE 754 floating point formats, together some key properties

A few comments are in order regarding Table 1. The quantity epsilon is defined
as being the smallest number than can be added to unity, with the result being
distinct from unity. Since floating point errors are relative, this can be
thought of as the relative error of a given floating point number. On the
largest and smallest numbers, we note that quantities evaluated on the lattice
will typically by $\mathcal{O}(1)$, with the smallest values typically being
$1/\kappa$, where $\kappa$ here is the condition number of the fermion matrix
we are solving for (and not the Wilson mass parameter). Thus we can observe
that it is unlikely we need the huge range afforded by double precision, even
if we may need the precision.

Similarly, we may also observe that both the precision and range of IEEE half
precision (FP16) are unlikely to be suitable for LQCD given that it would not
be possible to represent the dynamic range of a typical linear system to any
desirable precision. It is this that motivates the "half precision" format
that is used by QUDA. This is essentially a fixed-point representation, where
we utilize the entire 16-bit effective word size for precision, and do not
"waste" any bits for exponent bits. This is a natural fit for the gauge
fields, since these are elements of the special unitary group, and so all
values are guaranteed to be in the range $[-1,1]$.111The interested reader may
wonder what is done in the case of smeared gauge fields, where the matrix
elements are no longer necessary bounded as such. Here we simply compute the
global max field element, and use this to set the scale. For the fermion
fields, since these do not have an a priori bound, we compute the site-local
maximum absolute value and use this to set the scale. Once being loaded in
registers, the fields are converted into FP32 for computation. Hence the
format gives 16 bits of local precision, for an epsilon of $2^{-15}\sim
3\times 10^{-5}$ while at the same time giving a global dynamic range similar
to IEEE single precision.222One may wonder why we only have precision of
$2^{-15}$, as opposed to $2^{-16}$: this is because, unlike IEEE floating
point formats, we are using a signed integer twos-complement representation,
with no separate sign bit. Since LQCD computations consists of applying
(special) unitary rotations at the site level, a local fixed-point format is
in some sense optimal. In Listing 1 we illustrate the structure of the half-
precision format as deployed for a staggered fermion in QUDA.

⬇

1struct staggered_fermion_16 {

2 int16_t v[6];

3 float max;

4};

Listing 1: QUDA half-precision format for a staggered fermion

To avoid any confusion, from now on whenever we refer to half precision, we
are referring to the QUDA half precision format and not IEEE half precision.
Conversely, single and double precision do refer to their usual IEEE formats.

##  3 Mixed-Precision Solvers

In prior work [5], we reported on an efficient mixed-precision BiCGStab
method, where reliable updates [7] were utilized to ensure that the iterative
residual computed in the working, or sloppy, precision (typically half or
single) was periodically replaced with an explicitly computed residual in the
target precision (typically double).333How often the true residual should be
computed is a free parameter. For this work here we use $\delta=0.1$, e.g.,
each time the iterated residual drops by an order of magnitude we recompute
the true residual. We are presently experimenting with a more dynamic choice
based on explicit error estimation which may prove optimal [8]. While the
reliable-update mixed-precision method could also be applied naively to CG
with some limited success, this method was found to break down as the fermion
mass was decreased, e.g., condition number increases. Moreover, mixed-
precision methods have additional challenges when one is concerned with multi-
shift solvers. Since the solutions QUDA employs to both of these problems have
not previously been reported in the literature, we do so here.

###  3.1 Mixed-Precision Conjugate Gradient

An analysis of the breakdown of mixed-precision CG at small quark mass found
the issues were centred around a few key defects, which we now describe,
together with their respective solution.

  1. 1.

Accumulation of the partial solution vector in the sloppy precision leads to
unnecessary truncation of the solution vector. This can easily be remedied by
always storing the solution vector in high precision. For example, when using
a double-half CG solver, while the iterated residual and gradient vectors are
kept in half precision, the solution vector is stored in double precision. We
can mitigate the additional memory traffic overhead from storing the solution
vector in high precision by buffering the gradient vectors, and only
accumulating onto the solution vector periodically.

  2. 2.

While frequent correction of the residual vector with a reliable update cures
the residual drift, it does not prevent drift of the gradient vector. This
means that the super-linear acceleration factor of CG versus Steepest Descent
is lost, and the iteration count increases. This observation regarding the
gradient vector drifting was noted in [9] with a cure being given to re-
project the gradient vector whenever the residual is corrected.

  3. 3.

The computation of $\beta$, the coefficient used to ensure the gradient
vectors are A-orthogonal, breaks down when the Krylov space is constructed in
low precision. This has a similar effect as 2.) above, in that the super-
linear convergence of CG is lost. We stabilize the computation of $\beta$ by
adopting the Polak–Ribière formula from non-linear CG [10],

$\beta_{k+1}=\frac{r^{\dagger}_{k+1}(r_{k+1}-r_{k})}{r_{k}^{\dagger}r_{k}}.$

Note that in infinite precision, the additional term on the numerator
disappears since the residual vectors will be orthogonal, however, in finite
precision this additional term enhances the local orthonormality.

In Figure 1 we plot the residual history of the QUDA CG solver when solving
the staggered operator at a relatively light fermion mass. Shown on the plot
are the residual histories for a pure double-precision solver, a naive double-
half solver utilizing only reliable updates, and a double-half solver
utilizing the above three refinements. Dramatic improvement is evident,
demonstrating that these additions are critical to having a solver that
converges at all. The periodic jumps in the residual are indicative of a
reliable update taking place where the residual is recomputed in double
precision: that these jumps are mild for the stabilized algorithm indicates
that the residual drift is relatively well bounded.

Figure 1: Convergence history of CG solver ($V=16^{4}$, $\beta=5.6$,
$m=0.001$).

###  3.2 Mixed-Precision Multi-shift Conjugate Gradient

Multi-shift solvers rely on the shifted residuals being co-linear to the
unshifted base residual throughout the convergence [11], and this proves
troublesome when used in combination with mixed precision. While reliable
updates prevent drift of the unshifted residual, they do not prevent drift of
the shifted residuals. Thus over the course of the convergence, the shifted
residuals will cease to be co-linear with the unshifted residual, and the
shifted systems convergence stalls, even while the unshifted system retains
its convergence.

We are chiefly concerned with multi-shift CG, owing to its importance as the
primary solver when using Rational Hybrid Monte Carlo (RHMC) [12]. Prior to
this work, the optimal approach employed in QUDA has been to run the multi-
shift solver in double-single precision, employing reliable updates on the
unshifted system. As the iterated shifted residuals converge, or reach the
limit of the sloppy precision, we cease updating them and the solver is
terminated once all the shifted systems are removed. At this point we then
employ CG refinement, typically using double-half precision, solving the
unshifted system first, then refinement on the shifts. For the unshifted, we
preserve the gradient vector from the initial multi-shift solver, to retain
the Krylov space generated during the initial solve, and use a clean restart
for the shifted systems. Compared to a pure double-precision multi-shift
solver, we typically achieve around a 1.5-2$\times$ time-to-solution
improvement, with the speedup being tempered by the additional iterations
required due to the post-solve shifted system refinement.

###  3.3 The need for more precision

Even with the techniques and strategies described above there are limits to
how far one can push limited precision that cannot be so easily circumvented.

  * •

When the inverse of the condition number is smaller than the epsilon of the
precision employed, any linear solver will struggle since it will be unable to
simultaneously represent all eigenvalue scales to even a single significant
digit.

  * •

For solvers that require explicit orthogonalization, e.g., Arnoldi-based
methods, the size of Krylov space that can be constructed will be limited by
the precision of the representation.

  * •

As noted above, lack of precision in a mixed-precision multi-shift solve
results in a loss of co-linearity. Improving the sloppy precision could better
retain co-linearity in multi-shift solvers, reducing post-solve refinement
required, in turn maximizing the benefit of using mixed-precision solvers.

Thus we have motivation to consider how to improve the underlying precision of
the representation, or to maximize the precision at constant bit width.

##  4 Bit Packing for Lattice QCD

The idea of bit packing to achieve a reduced footprint is not a new one. A
recent work of note in the realm of HPC is ZFP [13] which is a lossy
compression library aimed at increasing the precision per bit achievable by
using a block storage format and utilizing the spatial coherence that
scientific data sets typically exhibit to achieve compression.

In the present case, let us reconsider the staggered fermion half precision
format (Listing 1). The primary value of the FP32 maximum component is the
8-bit exponent, as the 23 bits of mantissa and 1 bit sign add no value
relative to the other 16-bit components. A better approach is thus only
storing the exponent of the maximum value, and repurpose the remaining 24 bits
to improve the precision for all components. We sketch out such a storage
format in Listing 2, where we note we are abusing the C++ type naming
convention here to illustrate our point (there are no such types as int20_t or
int30_t). With this alternative format we have improved the precision of the
fermion components from 16 bits to 20 bits without any increase in memory
footprint, which should result in an epsilon of around $2^{-19}\sim 2\times
10^{-6}$.

⬇

1struct staggered_fermion_20 {

2 int20_t v[6];

3 uint8_t exponent;

4};

Listing 2: 20-bit precision format for a staggered fermion

Let us now consider the conventional single-precision format, which for a
staggered fermion would consist of six FP32 numbers, or 192-bits. Here we
again can use a shared exponent for all components, and repurpose the saved
bits for improving the effective precision. Listing 3 is a realization of
this, where we have improved the effective precision to 30 bits (from 24
bits), which should result in an epsilon of around $2^{-29}\sim 2\times
10^{-9}$.

⬇

1struct staggered_fermion_30 {

2 int30_t v[6];

3 uint8_t exponent;

4};

Listing 3: 30-bit precision format for a staggered fermion

Before we discuss implementation of these ideas and results, we note that the
above two example formats are just two of the many possible shared-exponent
formats that can be constructed: different solutions can be tailored as needs
change. Regarding the gauge field: owing to its lack of global dynamic range
we need no such special consideration. To accompany the 20-bit fermion we
simply utilize the 16-bit raw integer format used for half precision and for
the 30-bit format we utilize a 32-bit fixed point format.

Finally we note that a computation involving fermions and gauge fields will
require three precisions to be fully specified, and that any one of these can
be the precision limiter in a given computation:

  * •

The storage format of the gauge field, e.g., 16-bit, 32-bit, FP32

  * •

The storage format of the fermion field, e.g., 20-bit, 30-bit, FP32

  * •

The actual precision that the computation is done in, e.g., FP32, FP64

In the discussion below $\S\ref{sec:implementation}$, we use the triplet
shorthand of gauge precision / fermion precision / computation precision,
e.g., 16-bit / 16-bit / FP32 is the conventional QUDA half precision format,
and 16-bit / 20-bit / FP32 would be the new format using 20-bit fermions.

##  5 Implementation and Testing

###  5.1 Implementation

While the ideas sketched out in the prior section are easy enough to describe,
the fact that there are no native 20-bit and 30-bit integer types in C++ may
suggest that implementing such a format in an application framework such as
QUDA would be onerous, involving a lot of manual bit masking and shifting.
Fortunately, we can utilize bit fields [14] to easily address arbitrary
subsets of 32-bit words, effectively allowing for arbitrary precision types.
The notable exception here is in the case where we are required to partition a
given $n$-bit number between multiple (32-bit) words. For the interested
reader, in Appendix A we have included an example code listing which performs
the packing and unpacking of a staggered 20-bit fermion vector.

By virtue of the fact that QUDA uses opaque data accessors, providing an
abstraction layer between data order and the computation that uses this data,
none of these details leak into the high-level computation code: deploying
these bit-packed data types is merely a change in template instantiation.

###  5.2 Precision

In Figure 3 we plot the cumulative distribution function of the absolute
deviation of the HISQ Dslash, running on an NVIDIA GPU, using as reference a
distinct FP64 implementation running on a host CPU. For the 20-bit format we
see only a modest improvement versus half precision: this is not surprising
since in this case we are still using a 16-bit gauge field. For 30-bit, we see
that we must perform the computation using FP64, else we see effectively
unchanged precision versus a pure FP32 implementation. Notably, we see that
the 30-bit format, together with FP64 computation achieves around two orders
of magnitude additional precision versus pure FP32, with errors $\sim 10^{-9}$
as we would expect from our epsilon expectations for the 30-bit format.

Figure 2: CDF of the absolute deviation for the application of the HISQ
operator to a random source vector ($V=36^{3}\times 72$, $\beta=6.3$,
$m=0.001$)).

Figure 3: Performance in GFLOPS for the application of the HISQ operator on a
Quadro GV100 ($V=32^{4}$).

###  5.3 Performance

Clearly there is a non-trivial overhead from using these bit-packed data types
compared with using the usual IEEE floating point formats. Thus, even if these
formats provide significantly more precision, it may not prove to be a net
gain. In Figure 3 we plot the performance of the QUDA HISQ dslash on an NVIDIA
GPU. We see the desired behaviour, that the overhead of using these bit-packed
formats is negligible, and performance is essentially identical to the
equivalent legacy formats. It is noteworthy that with the 30-bit format, we
can afford the additional packing / unpacking, as well performing all
computation using FP64, and yet still have the same performance as pure FP32.
Of course, this statement will be an architecture-dependent one: different
architectures can have differing ratios of floating point to integer
throughput, and the significant increase in integer processing requirements
for unpack and packing these formats could prove significant on other
architectures.

##  6 Solver Results

In this section we give some examples that illustrate the improved convergence
possible from using these bit-packed formats. For brevity we refer to the
16-bit / 20-bit / FP32 format simply as "20-bit" and similarly the 32-bit /
30-bit / FP64 format as "30-bit". The results here are illustrative, not
definitive, and for this initial technology demonstration we use only a single
gauge configuration taken from the NERSC medium benchmark set [15].

###  6.1 BiCGStab($l$)

The BiCGStab($l$) solver is an enhancement over the BiCGStab solver in that it
extends the single iteration MR minimization to $l$ iterations of GCR
minimization [16]. Thus each $l$ steps we are required to orthogonalize an
$l$-length vector set. In principle a greater value of $l$ will lead to
smoother convergence, however, lack of precision in the orthogonalization can
result in solver breakdown. In Figure 5 we plot the convergence history from
using BiCGStab(4) for the HISQ staggered operator using pure double, double-
single, double-int30, double-int20, and double-half mixed-precision solvers.
The corresponding time to solution and iteration counts are shown in Table 5.
We see improved convergence for double-int30 versus double-single resulting in
a reduced time to solution. The stand out improvement comes from double-int20
versus double-half, where we see the improved precision from the vectors
(fermions) alone dramatically stabilizes the solver convergence leading to the
optimal approach. We attribute this improvement to the increased stability of
orthogonalization in the solver.

Figure 4: Convergence history of BiCGStab(4) solver for the HISQ operator
($V=36^{3}\times 72$, $\beta=6.3$, $m=0.001$)).

| iter | Time (s)
---|---|---
pure double | 26064 | 307
double-single | 27308 | 159
double-int30 | 26580 | 150
double-int20 | 29336 | 106
double-half | 67552 | 247

Figure 5: Iterations and time to solution for the results shown in Figure 5.

###  6.2 Multi-shift CG

For the baseline we deploy the mixed-precision strategy as described in
$\S$3.2, and compare this to an improved variant where we run the initial
multi-shift solver in double-int30 (as opposed to double-single) and the
refinement CG solver now uses double-int20 (opposed to double-half). In Table
2 we compare the iteration counts for an example multi-shift CG solve.444This
is taken from a light quark solve in RHMC, each shift has a unique target
residual here where the tolerance is set to optimize for the resulting force
contribution [17]. For both approaches we see it is the intermediate shifts
that require the greatest refinement iterations: this is because they are far
enough away from the unshifted system that their residuals have drifted
sufficiently, while at the same time not being heavy enough to have fast
convergence. For the unshifted system we see virtually identical convergence
for new versus old. However, when we look at the shifted systems we see in all
cases more than an order of magnitude reduction in the residual. As a result
we see a dramatic reduction in the additional refinement iterations required,
going from hundreds of iterations required per shift to a few dozen per shift.
The overall effect is a reduction in total number of operator applications by
around 13%.

| double-single-half | double-int30-int20 | target residual
---|---|---|---
shift | iter | $r_{\sigma}$ | iter | $r_{\sigma}$ |
(multi-shift) | 8728 | - | 8726 | - | 1.00e-05
0 | 2323 | 8.91e-05 | 2320 | 8.92e-05 | 1.00e-05
1 | 40 | 4.82e-03 | 10 | 2.62e-04 | 1.75e-05
2 | 113 | 1.82e-03 | 12 | 9.93e-05 | 3.86e-05
3 | 432 | 6.14e-04 | 15 | 3.33e-05 | 8.85e-05
4 | 411 | 1.95e-04 | 18 | 1.06e-05 | 2.05e-08
5 | 323 | 6.08e-05 | 22 | 3.29e-06 | 4.81e-09
6 | 232 | 1.87e-05 | 44 | 1.01e-06 | 1.15e-09
7 | 158 | 5.64e-06 | 60 | 3.01e-07 | 2.50e-10
8 | 114 | 2.03e-06 | 56 | 1.04e-07 | 4.64e-11
9 | 81 | 9.10e-07 | 45 | 4.24e-08 | 1.30e-11
10 | 64 | 5.96e-07 | 37 | 2.41e-08 | 6.85e-12
total | 13019 |  | 11365 |  |
Table 2: Multi-shift and subsequent refinement CG solver iteration counts:
shift 0 represents a continuation of the multi-shift solve but on the
unshifted system only. For each shift we show the true residual after the
initial multi-shift solve $r_{\sigma}$ and the target residual
($V=36^{3}\times 72$, $\beta=6.3$, $m=0.001$).

##  7 Conclusion

In this work we have introduced LQCD-specific storage formats that achieve
more precision at fixed bit width compared to the conventional IEEE floating
point formats. Given the bandwidth-bound nature of LQCD computations, this
method can be an important optimization approach. The effect on mixed-
precision solvers was illustrated, where we observe we can reduce the total
number of iterations at fixed bit width without any significant raw
performance impact.

This work is just an initial investigation and there a number of possible
applications for these techniques. Beyond solver stabilization, one
application could be offline storage using more efficient bit-packed formats
for storing gauge fields or propagators. One interesting application may be
for extending beyond double precision: present-day LQCD computations are
starting to bump up against the precision limits of IEEE double precision,
with some gauge generation implementations now selectively utilizing 128-bit
precision floating point precision [18], whether it be true quad or double-
double. As the need for extended precision increases, an alternative would be
to use a Tailor-made precision format with just the right amount of precision
for the application at hand.

##  Appendix A Example: 20-bit staggered fermion vector

We include the C++ code below as an example of how to implement the packing
and unpacking for a 20-bit staggered fermion. One implementation detail we
call out: while we have signed numbers in general, bit shifting should be done
with unsigned integers to prevent undefined behaviour.

⬇

1 template <unsigned int B, typename T> T signextend(const T x) {

2 struct {T x:B;} s;

3 s.x = x;

4 return s.x;

5 }

6

7 union float_structure {

8 float f;

9 struct float32 {

10 unsigned int mantissa : 23;

11 unsigned int exponent : 8;

12 unsigned int sign : 1;

13 } s;

14 };

15

16 template <> struct alignas(16) spinor_packed<20> {

17 static constexpr unsigned int bitwidth = 20;

18 static constexpr float scale = 524287; // 2^19 - 1

19

20 // the struct consists of 4x 32 bit words

21 unsigned int a_re : 20;

22 unsigned int a_im_hi : 12;

23

24 unsigned int a_im_lo : 8;

25 unsigned int b_re : 20;

26 unsigned int b_im_hi : 4;

27

28 unsigned int b_im_lo : 16;

29 unsigned int c_re_hi : 16;

30

31 unsigned int c_re_lo : 4;

32 unsigned int c_im : 20;

33 unsigned int exponent : 8;

34

35 // Pack a 3 component complex vector into this

36 template <typename spinor> void pack(const spinor &in) {

37 // find the max

38 float max = {fabsf(in[0].real()), fabsf(in[0].imag())};

39 for (int i = 1; i < 3; i++) {

40 max = fmaxf(max, fabsf(in[i].real()));

41 max = fmaxf(max, fabsf(in[i].imag()));

42 }

43

44 // compute rounded up exponent for rescaling

45 float_structure fs;

46 fs.f = max[0] / scale;

47 fs.s.exponent++;

48 fs.s.mantissa = 0;

49 exponent = fs.s.exponent;

50

51 // negate the exponent to avoid the division below

52 fs.s.exponent = -(fs.s.exponent - 127) + 127;

53

54 // rescale and convert to integer

55 int vs[6];

56 for (int i = 0; i < 3; i++) {

57 vs[2 * i + 0] = lrint(in[i].real() * fs.f);

58 vs[2 * i + 1] = lrint(in[i].imag() * fs.f);

59 }

60

61 unsigned int vu[6];

62 for (int i = 0; i < 6; i++) memcpy(vu + i, vs + i, sizeof(int));

63

64 // split into required bitfields

65 a_re = vu[0];

66 a_im_hi = vu[1] >> 8;

67

68 a_im_lo = vu[1] & 255;

69 b_re = vu[2];

70 b_im_hi = vu[3] >> 16;

71

72 b_im_lo = vu[3] & 65535;

73 c_re_hi = vu[4] >> 4;

74

75 c_re_lo = vu[4] & 15;

76 c_im = vu[5];

77 }

78

79 // Unpack into a 3-component complex vector

80 template <typename spinor> void unpack(spinor &v) {

81 // reconstruct 20-bit numbers

82 unsigned int vu[6];

83 vu[0] = a_re;

84 vu[1] = (a_im_hi << 8) + a_im_lo;

85 vu[2] = b_re;

86 vu[3] = (b_im_hi << 16) + b_im_lo;

87 vu[4] = (c_re_hi << 4) + c_re_lo;

88 vu[5] = c_im;

89

90 // convert to signed

91 int vs[6];

92 for (int i = 0; i < 6; i++) memcpy(vs + i, vu + i, sizeof(int));

93

94 // signed extend to 32 bits and rescale

95 float_structure fs;

96 fs.f = 0;

97 fs.s.exponent = exponent;

98

99 using real = decltype(v[0].real());

100 for (int i = 0; i < 3; i++) {

101 v[i].real(static_cast<real>(signextend<bitwidth>(vs[2 * i + 0])) * fs.f);

102 v[i].imag(static_cast<real>(signextend<bitwidth>(vs[2 * i + 1])) * fs.f);

103 }

104 }

105 };

Listing 4: 20-bit format for a staggered fermion

## References

  * [1] M. Smelyanskiy, K. Vaidyanathan, J. Choi, B. Joó, J. Chhugani, M.A. Clark et al., _High-performance lattice QCD for multi-core based parallel systems using a cache-friendly hybrid threaded-MPI approach_ , in _SC ’11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis_ , pp. 1–10, 2011, DOI.
  * [2] M.A. Clark and R. Babich, _High-efficiency Lattice QCD computations on the Fermi architecture_ , in _2012 Innovative Parallel Computing (InPar)_ , pp. 1–9, 2012, DOI.
  * [3] M.A. Clark, A. Strelchenko, A. Vaquero, M. Wagner and E. Weinberg, _Pushing Memory Bandwidth Limitations Through Efficient Implementations of Block-Krylov Space Solvers on GPUs_ , _Comput. Phys. Commun._ 233 (2018) 29 [1710.09745].
  * [4] G.I. Egri, Z. Fodor, C. Hoelbling, S.D. Katz, D. Nógrádi and K.K. Szabó, _Lattice QCD as a video game_ , _Computer Physics Communications_ 177 (2007) 631.
  * [5] M.A. Clark, R. Babich, K. Barros, R.C. Brower and C. Rebbi, _Solving Lattice QCD systems of equations using mixed precision solvers on GPUs_ , _Comput. Phys. Commun._ 181 (2010) 1517 [0911.3191].
  * [6] _IEEE Standard for Floating-Point Arithmetic_ , _IEEE Std 754-2019 (Revision of IEEE 754-2008)_ (2019) 1.
  * [7] G. Sleijpen and H. van der Vorst, _Reliable updated residuals in hybrid Bi-CG methods_ , _Computing_ 56 (1996) 141.
  * [8] H.A. van der Vorst and Q. Ye, _Residual Replacement Strategies for Krylov Subspace Iterative Methods for the Convergence of True Residuals_ , _SIAM Journal on Scientific Computing_ 22 (2000) 835 [https://doi.org/10.1137/S1064827599353865].
  * [9] R. Strzodka and D. Goddeke, _Pipelined Mixed Precision Algorithms on FPGAs for Fast and Accurate PDE Solvers from Low Precision Components_ , in _2006 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines_ , pp. 259–270, 2006, DOI.
  * [10] E. Polak and G. Ribière, _Note sur la convergence de méthodes de directions conjuguées_ , _Revue Française d’Automatique, Informatique, Recherche Opérationnelle_ 3 (1969) 35.
  * [11] B. Jegerlehner, _Krylov space solvers for shifted linear systems_ , 1996\.  10.48550/ARXIV.HEP-LAT/9612014.
  * [12] M.A. Clark and A.D. Kennedy, _Accelerating Dynamical-Fermion Computations Using the Rational Hybrid Monte Carlo Algorithm with Multiple Pseudofermion Fields_ , _Physical Review Letters_ 98 (2007) .
  * [13] P. Lindstrom, _Fixed-Rate Compressed Floating-Point Arrays_ , _IEEE Transactions on Visualization and Computer Graphics_ 20 (2014) 2674.
  * [14] CPP Reference contributors, “Bit-field.” https://en.cppreference.com/w/cpp/language/bit_field, 2022.
  * [15] QUDA contributors, “Running the NERSC MILC Benchmarks.” https://github.com/lattice/quda/wiki/Running-the-NERSC-MILC-Benchmarks, 2022\.
  * [16] G.L. Sleijpen and D.R. Fokkema, _BiCGstab (ell) for linear equations involving unsymmetric matrices with complex spectrum_ , _Electronic Transactions on Numerical Analysis._ 1 (1993) 11.
  * [17] M.A. Clark, P. de Forcrand and A.D. Kennedy, _Algorithm Shootout: R versus RHMC_ , .
  * [18] M. Lüscher, “openQCD.” https://luscher.web.cern.ch/luscher/openQCD.


# Can ChatGPT Pass a Theory of Computing Course?

Matei A. Golesteanu<EMAIL_ADDRESS>United States Military
AcademyWest PointNew YorkUSA ,  Garrett B. Vowinkel
<EMAIL_ADDRESS>United States Military AcademyWest PointNew
YorkUSA and  Ryan E. Dougherty<EMAIL_ADDRESS>0000-0003-1739-1127 United States Military Academy601 Thayer RoadWest PointNew
YorkUSA10996

(2018; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

Large Language Models (LLMs) have had considerable difficulty when prompted
with mathematical questions, especially those within theory of computing (ToC)
courses. In this paper, we detail two experiments regarding our own ToC course
and the ChatGPT LLM. For the first, we evaluated ChatGPT’s ability to pass our
own ToC course’s exams. For the second, we created a database of sample ToC
questions and responses to accommodate other ToC offerings’ choices for topics
and structure. We scored each of ChatGPT’s outputs on these questions.
Overall, we determined that ChatGPTcan pass our ToC course, and is adequate at
understanding common formal definitions and answering “simple”-style
questions, e.g., true/false and multiple choice. However, ChatGPT often makes
nonsensical claims in open-ended responses, such as proofs.

theoretical computer science, computer science education, large language
model, formal languages, automata theory, chatgpt

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Theory of computation Formal languages and automata theory††ccs: Social and
professional topics Computing education††ccs: Mathematics of computing
Discrete mathematics

##  1\. Introduction

Large Language Models (LLMs) have had a serious impact on student academic
integrity, including Computer Science. Many LLMs train based upon publicly
available data, which is proportional to the popularity of students taking
courses in certain topics. In terms of CS, the most popular topic is
introductory programming. However, for less popular topics, do LLMs perform as
well, especially in technical topics that require precise arguments and are
rigorous?

This paper attempts to answer this question for a Theory of Computing (ToC)
course, which is a required course for nearly all undergraduate CS curricula.
It is a traditionally difficult course as it nearly always requires students’
be able to write precise proofs and create mathematical constructions. We
tested the ChatGPT LLM111http://chatgpt.com/ within the ToC course at our
institution in two different experiments. First, we tested its ability to pass
our course’s exams by grading its responses as though it were an actual
student. Second, we created a large database of representative questions other
offerings of ToC may ask, and determine ChatGPT’s ability to answer those
questions.

Our methods attempt to model what a student would do if they were in a ToC
course and used ChatGPT. The goals of this work are to (1) inform educators on
ChatGPT’s ability to pass a ToC course, (2) also inform eductors what they can
do to limit students’ ability to use ChatGPT without their learning ToC
concepts, and (3) if desired, determine where ChatGPT struggles to help inform
future ToC course designs on how to make LLM tools be more effective in the
classroom. The remainder of this paper is organized as follows.

  * •

Section 2 contains related work to ours.

  * •

Section 3 contains our method, which involves these two experiments.

  * •

Section 4 contains our results to our two experiments.

  * •

Section 5 discusses our results that will inform ToC educators of what aspects
of ToC ChatGPT struggled with the most.

  * •

Section 6 contains our threats to validity.

  * •

Section 7 contains our recommendations to educators and future work.

  * •

Section 8 concludes the paper.

##  2\. Background Research

As far as we are aware, there has not been any prior research with ChatGPT’s
ability to pass a ToC course. However, there has been several works regarding
other common CS courses. Sharpe et al. (Sharpe et al., 2024) recently
determined that ChatGPT can easily pass a CS1 course. Banerjee et al.
(Banerjee et al., 2023) discussed “different opportunities with use cases of
ChatGPT in augmenting the learning experience.” The paper proposes several
methods in order to integrate the use of AI’s into the classroom, such as
having students explain an answer given by ChatGPT, or explain the logic used
by ChatGPT. Echeverría et al. (Rodriguez-Echeverría et al., 2024) conducted an
analysis of ChatGPT’s performance in computer engineering exams, and found
that ChatGPT can effectively pass that class even though it contained many
different types of questions.

Although not directly a CS topic, a closely related work to ours is that of
Frieder et al. (Frieder et al., 2024), about ChatGPT’s ability to answer
discrete math questions; this course is very often a pre-requisite for ToC.
They determined that ChatGPT can reasonably well solve undergraduate-level
problems, but not graduate-level ones. Relevant to our work, they used ChatGPT
version 4, as it is more accurate than previous versions of ChatGPT; we will
be using this version.

Research was also done into using “prompt engineering” in order to tailor
ChatGPT’s responses to make them more accurate. Velásquez-Henao et al.
(Velásquez-Henao et al., 2023) describe “a methodology for optimizing
interactions with Artificial Intelligence language models”. They found that by
using specific, creatively framed questions for ChatGPT, they could
effectively “elicit precise, accurate, and contextually appropriate
responses.” We adopt a similar approach of prompt engineering to improve
ChatGPT’s responses.

##  3\. Course Context and Method

Our institution is a small liberal-arts college (SLAC) located in the
northeastern United States, with between 30 and 50 CS students graduating
every year. Our ToC course consists of five main sections: (1) regular
languages, (2) context-free languages, (3) Turing Machines and Decidability,
(4) Undecidability, and (5) NP-Completeness. The formal pre-requisites are
discrete mathematics and data structures, a CS2 course; an informal pre-
requisite is programming languages as it helps with some formal notation.
There are no formal post-requisites, but students very often take a year-long
capstone course and an Operating Systems course in the next semester.

For both experiments and the results we give below, there are many acronyms
and phrases that we use for terms in our ToC course, which are very standard.
For simplicity, Table 1 has a mapping from acronym or shortened phrase to its
meaning; for a refresher on the formal definitions of these terms, see Sipser
(Sipser, 2013).

Table 1. Acronyms and shortened phrases used throughout our ToC course and this paper. Acronym | Meaning
---|---
CFG | Context-Free Grammar
Count | Countability
CNF | Chomsky Normal Form
Dec. | Decidable
DFA | Deterministic Finite Automaton
DPDA | Deterministic Pushdown Automaton
Induct | Structural Induction
NFA | Nondeterministic Finite Automaton
NP | Nondeterministic Polynomial Time
PDA | Pushdown Automaton
PL | Pumping Lemma
Rec. | Recognizable
Regex | Regular Expression
Rice | Rice’s Theorem
TM | Turing Machine
Undec. | Undecidable

###  3.1. Experiment 1: ChatGPT in our ToC Course

Student assessment for our course was divided up as follows:

  * •

Paper Writing: 450 points

  * •

Two Midterm Exams: 200 points total

  * •

Formal Group Presentation: 100 points

  * •

Final Exam: 250 points

The paper writing assessment is an extension based on the work of Dougherty
(Dougherty, 2024), involving writing a research paper in small groups across
the semester using knowledge gained in our ToC course. The formal group
presentation is based on the fifth section of our ToC course, namely NP-
Completeness. Students had to give a full proof based on a given proof from
the Garey and Johnson textbook (Garey and Johnson, 1979), which omits some
details. Finally, the midterms and final are standard in-class exams.

In Dougherty’s method (and ours), the paper topics are different for each
group; the same is true of the formal group presentation. Therefore, we
determine whether ChatGPT can adequately pass the three exams. The results we
find would be applicable to many other institutions and course contexts
because many ToC courses have a very heavy weight to exams; further, these
exams test students’ baseline understanding of the material.

The first midterm exam only covered Section 1 (regular languages), the second
exam only covered Section 2 (context-free languages), and the final exam
covered all 5 sections. As for individual topics, Midterm 1 contained
questions about induction, DFAs, NFAs, NFA to DFA conversion, the Pumping
Lemma for Regular Languages, and regular expressions. Midterm 2 contained
questions about Context-Free Grammars, Pushdown Automata, conversions between
these two models, the Pumping Lemma for Context-Free Languages, and
Deterministic Pushdown Automata. And finally, the Final Exam contained
questions including topics from Midterms 1 and 2, and Turing Machines,
Countability, Decidability, Undecidability, and NP-Completeness.

###  3.2. Experiment 2: Question Database

We do note that ToC course contexts do vary in terms of topics tested, even
within the five sections mentioned above. For example, some ToC courses may
teach the Pumping Lemma for Regular Languages, and some may instead choose the
Myhill-Nerode equivalence relation. Further, the three exams may not be as
comprehensive for detailing specifically in which concepts ChatGPT performs
well as they are a limited-time environment. Therefore, in addition to the
results we find for our own specific ToC course, we also compiled many
different ToC questions to cover a larger spectrum of what other ToC offerings
may have.

We focus on the first four sections of our ToC as these sections on a macro
level are very widespread across ToC course offerings. Here, we created 450
questions about basic topics in ToC, evenly divided among (1), (2), and (3) +
(4). These questions were evenly divided amongst True/False, Multiple Choice,
and Proof question types. The design of these questions is suitable for an
undergraduate-level ToC course; some are based on definitions of formal
objects, some on simple properties of the given language or model, asking
ChatGPT to provide examples of a language/model, etc. Here is a sample of our
generated questions:

  * •

”Is the complement of a regular language also a regular language? Justify your
answer.”

  * •

”True or false: No arbitrarily long language can ever be regular.”

  * •

”Prove that the language $L2=\\{0^{a}1^{b}:a>b\\}$ is not regular using the
pumping lemma.”

  * •

”What is the formal definition of a Deterministic Finite Automata?”

  * •

”Give an example of a language that a DFA cannot model?”

  * •

”True or false: There exists an NFA such that it cannot be converted to a
DFA.”

  * •

”Give a recursive definition for the following set: the set $X$ of all strings
in $\\{0,1\\}^{\star}$ containing 00.”

  * •

”True or False: the transition function of a pushdown automata is the same as
that of an NFA.”

  * •

”True or false: the pumping lemma for context free languages can be used to
shown that a language is context free.”

  * •

”What is the formal definition of a context free grammar?”

We then fed all of the questions into ChatGPT using a set precursor message
before every prompt: “I will ask you a question to test your academic
theoretical computer science knowledge, answer to the best of you abilities.
Here it is:”. After receiving and recording the responses, we assigned them a
grade from 0–4 based on a rubric. It is important to note that we did not
grade simply the response in the case of True/False or Multiple Choice
questions, but also the reasoning and correctness behind the responses.
Therefore, it is possible that it chose the correct option, but did not earn a
4/4 due to the reasoning/correctness. The rubric is as follows:

  * •

4: Totally correct and complete solution, covering all aspects of the
question, and answered with enough depth to warrant full points on an
undergraduate-level ToC exam.

  * •

3: Mostly correct and mostly complete solution. This covers answers that are
mostly correct, but have minor mistakes; these can include not fully answering
minor parts of the question, slight missteps in a proof, or otherwise making
some small error which does not detract from the overall answer, but would
also not earn full points on an undergraduate-level ToC exam.

  * •

2: This grade will be given to responses that have a somewhat correct answer
but include a major flaw. This could include proofs that arrive to a correct
conclusion or mostly adhere to a correct logical flow, but make some large
incorrect assumption or step which detracts from the overall value.

  * •

1: This grade is the equivalent of a 3 but on the opposite side, being a
mostly incorrect or incomplete solution. The grade covers responses which have
some semblance of truth and correctness, but still make a large error in
either proof or justification.

  * •

0: Completely wrong answer. This grade will be given to a response if it is
absolutely incorrect and does not even begin to contain some truthful aspect
or a path towards the correct answer.

ChatGPT was then given the opportunity to try again if it did not score a 4/4.
Basic feedback given to ChatGPT in the following form: “You got a x/4, improve
the answer.”, with x being the appropriate rubric score. A maximum of three
attempts were given for each question. The feedback is purposefully consistent
and vague.

###  3.3. Experimental Setup

In both experiments, none of the questions used deception to induce ChatGPT to
produce false answers. We used ChatGPT version 4 as it is the most accurate
currently available model and we could upload a document directly. Many of the
questions require mathematical notation; see the sample questions above for
examples. However, an easily readable notation is not directly compatible with
ASCII characters normally typed in on a keyboard. For Experiment 1, as we are
using ChatGPT 4, we directly uploaded the exams as Word documents to ChatGPT
to avoid this issue; for realism purposes, these exams were identical to those
given to the ToC students at our institution. For Experiment 2, we formatted
the questions as close as possible to the formal notation with ASCII
characters; no question in this data set required a diagram for the prompt.
For example, consider the third example question above about showing that
$L2=\\{0^{a}1^{b}:a>b\\}$ is not regular; what we instead used for this prompt
was `L2 = {0^a 1^b : a > b}`. In both experiments, only a few times did
ChatGPT not understand the initial prompt, and every issue was corrected with
a clarifying prompt. One example is in Experiment 1 when ChatGPT interpreted
$\sigma^{i}$ for $\sigma_{i}$.

##  4\. Results

Table 2 contains our overall results for Experiment 1. For each of the three
exams, it contains the scores for both the verbatim questions in the exam and
revised answers after trying again when given a hint as to why the answer it
gave is wrong. Overall, ChatGPT performed well on all three exams, earning
over 80% in all experiments, and up to 93% after re-tries with helpful hints.
The weighted average was equivalent at our institution to a B- as the initial
letter grade, and an A- after re-tries. Each of the exams contains “main”
questions and “bonus” questions; the listed scores in our results include
these bonus questions for accuracy.

Table 2. Overall results for Experiment 1. | Initial | After Retry
---|---|---
Midterm 1 (Section 1) | 80.5% | 93.0%
Midterm 2 (Section 2) | 87.5% | 92.0%
Final Exam (Sections 1–5) | 81.0% | 88.6%
Average | 82.33% | 90.33%

Table 3 contains our overall results for Experiment 2. It shows the average
best score for each topic tested. Here, “Average Max” refers to the mean of
all of the scores, where the score for each question is the best attempt on
that particular question. Overall, ChatGPT earned an 85% for Experiment 2;
this is 91.5% on true/false questions, 87.3% on multiple choice questions, and
78.8% on proof-type questions.

Table 3. Results for Experiment 2; we show the average maximum score obtained for each of the 450 questions we asked ChatGPT including re-tries, as well as the average across question types and categories. Indicated cells show when the average grade is below failing at our institution. For the meaning of each of the acronyms and short phrases, see Table 1.  | Section 1 | Section 2 | Section 3 | Section 4 |  |
---|---|---|---|---|---|---
| Induct | DFA | NFA | PL | Regex | CFG | PDA | CNF | DPDA | PL | TMs | Count | Dec., Rec. | Undec. | Rice | Avg. |
T/F | 3.7 | 4.0 | 3.4 | 3.8 | 3.4 | 4.0 | 3.8 | 3.6 | 3.7 | 3.6 | 3.6 | 3.6 | 3.4 | 3.7 | 3.6 | 3.66 |
MC | 3.8 | 4.0 | 3.3 | 3.1 | 3.4 | 3.2 | 3.9 | 3.5 | 3.5 | 3.7 | 3.3 | 3.6 | 3.0 | 3.3 | 3.7 | 3.49 |
Proof | 3.2 | 3.7 | 3.0 | 3.4 |  2.4 |  2.5 |  2.5 | 3.6 | 3.4 | 3.4 |  2.4 | 3.5 | 3.4 | 3.4 | 3.4 | 3.15 |
Avg. | 3.57 | 3.90 | 3.23 | 3.43 | 3.07 | 3.23 | 3.40 | 3.57 | 3.53 | 3.57 | 3.10 | 3.57 | 3.27 | 3.47 | 3.57 |  |

##  5\. Discussion

###  5.1. Experiment 1 Discussion

For brevity we will not include a discussion of each question individually,
but rather include any discussion that will be of use for educators and/or
gave surprising results.

ChatGPT could read state diagram pictures correctly, but this heavily depended
on the picture’s format. For example, in the induction question for Midterm 1,
students needed to observe a state diagram of a DFA given as a JPG picture
included in the exam Word document; here, ChatGPT read that picture correctly.
However, in the same exam’s third question, about a standard NFA to DFA
conversion, the state diagram was directly drawn in Word using its built-in
shapes, and not as a JPG image. As a result, ChatGPT was unable to correctly
read the picture even after a re-try, although some of the transitions and
state names were correct; see Figure 1 for the initial table. In this case, we
resorted to directly giving ChatGPT the transition table, after which it
performed the conversion correctly. For all other questions that used Word’s
built-in equation editor, ChatGPT read the equation perfectly.

ChatGPT’s approach for “wrong” answers was often very incremental, and never
attempted to diagnose any core issue with its initial reasoning. For example,
Midterm 1’s second question involved creating a small DFA for a given
language. ChatGPT’s initial solution with 4 states was incorrect, but was
fixed after a re-try. The interesting part here is that ChatGPT’s correct DFA
still had 4 states, whereas the “model” solution only needed 3; here, the 4th
state was unreachable and so was “useless.”

(a) Original NFA for Midterm 1’s third question.

(b) Initial Table from ChatGPT.

Figure 1. Example of ChatGPT’s issue with reading state diagrams directly made
in Word.

In general, as expected, ChatGPT performed well at questions that are nearly
identical to those that are posted online for which it could train on, and
very poorly on questions that are not. ChatGPT frequently ran into trouble
even in the first case because small deviations in question phrasing can yield
large changes in the answer as the underlying meaning could change. For
example, consider the question: “True or False: the complement of the language
$\\{a^{n}b^{n}c^{n}:n\geq 0\\}$ is context-free.” The answer is true and is a
standard exercise to prove it (as is similar to a true/false with explanation
question in Midterm 2); however, if the ending was changed to “deterministic
context-free”, then the answer is false for a completely different reason.

Often the culprit for poorly performed questions is the notion of
“universality,” in treating every case. For example, the Pumping Lemma
question in both Midterms involved showing a given language is either not
regular or not context-free; to adequately do so, all possible cases of
decomposing a string needed to be considered. In neither case did ChatGPT
handle all such cases. Whenever a question is “existential” in that one needs
to perform an algorithm on a given DFA, or give an example CFG, then ChatGPT
performs much better. ChatGPT performed better still when questions were
phrased in a direct format without any ambiguity in the truth of the answer,
e.g., “Prove that $L$ is regular” vs. “True or False: $L$ is regular.”

ChatGPT’s reasoning for proof-type problems is very rarely formal. An example
is on the Final Exam where a short answer question involved determining if
there is an algorithm for solving a given problem, such as checking if a
Turing Machine halts on all inputs within a fixed number of steps. Much of
ChatGPT’s reasoning here involved loosely arguing why there was no such
algorithm because one needed to consider “all inputs”, even though there was a
bound on how many tape cells can be visited (thus not all inputs even need to
be considered). In a majority of cases, however, ChatGPT either corrected or
partially addressed its answers here after a re-try.

ChatGPT sometimes treated parts of problems as “black boxes” even if they are
referential to other parts. For example, the Final Exam had a Rice’s theorem
application question, where students needed to determine if that theorem
applies. In this case, it does not because the input to the problem is a
Turing Machine, and the language involved the TM accepting two different
strings; a given one, and the machine’s own description. This second string
forces Rice’s theorem to not apply as it breaks one of the theorem’s
conditions. Like nearly all of our ToC students, ChatGPT treated the TM’s own
description as any other ordinary string not dependent on the input, and
concluded the theorem could be applied.

There were a handful of cases where ChatGPT completely “understood” the prompt
(i.e., the question was reproduced perfectly), and the exercise was standard,
but nevertheless ChatGPT made a simple mistake. For example, the first
question of Midterm 2 involved creation of a CFG that involves breaking the
problem down into usage of three key components: closure under union, such as
$L_{1}\cup L_{2}$ where both languages are context-free; nesting, such as
$\\{a^{n}b^{m}c^{m}d^{n}:n,m\geq 0\\}$; and multiple parts, such as
$\\{a^{n}b^{n}c^{m}d^{m}:n,m\geq 0\\}$. ChatGPT treated the “multiple part”
aspect of the question as a “nesting” one, although after a re-try it
corrected the mistake.

###  5.2. Experiment 2 Discussion

Again for brevity, we will not discuss every question, but rather highlights.
ChatGPT had the highest average with DFA-related questions, and the lowest
average with Regex-related questions. This could be due to the type of
question in each category. The questions for DFA’s ended up being largely
definitions, with a few being practice problems, as it is the first topic
within Section 1 of our ToC course, and its definition is more involved than
the Regex definition. Consequently, the problems for Regex were largely
practice problems that required a larger amount of creativity and critical
thinking, and not just surface-level application of the definitions of topics.

There were rare cases where the explanation and reasoning were very close to
being fully correct, but some small error lead to ChatGPT’s final answer being
wrong; this was implied in our discussion about Experiment 1. These cases
occurred especially with the proof questions, as there are many more
opportunities within proof steps to be wrong, particularly with induction,
Pumping Lemma, and Undecidable reduction proofs.

ChatGPT is often very malleable in its responses, which would make specific
feedback prone to being interpreted as a hint, leading to ChatGPT changing its
answer to fit what the feedback is saying. By being vague we attempt to ensure
that the knowledge being tested reflects only what ChatGPT currently
possesses.

ChatGPT sometimes altered its response with a worse score than its initial
guess by adding useless information to the question’s intent. For example, one
question asked to determine if a given CFG is ambiguous, which involved
showing two leftmost derivations of the same string. ChatGPT understood this,
but produced two derivations of two different strings that were very similar
to each other, but not the same. In the re-try, ChatGPT gave the same output
along with a derivation of another string that was completely unrelated to
what the question was asking.

###  5.3. Effects of Prompt Engineering

To understand prompt engineering’s influence, we determine its effects on the
30 NFA questions; Table 3 shows that the average score on these questions was
3.23. Using the same rubric as Experiment 2, we tested the same questions with
the following initial prompt:

> I want you to respond like you are the preeminent computer science professor
> in the world. You will give intuitive and complete responses to my
> questions. You will be given a series of questions designed to test your
> ability to answer such questions. You will respond methodically and give
> your complete reasoning for every question. I will give you feedback with a
> score out of 4, and you will improve your answer using my feedback as a
> guide for how much your answer was incorrect.

We found that the average score on these questions rose to 3.53. On average,
the true/false questions had an increase to 3.6 (vs. 3.4), the multiple-choice
questions increased to 3.9 (vs. 3.3), and the proof questions increased to 3.1
(vs. 3.0). It is clear the prompt engineering had a much larger effect on the
multiple-choice questions. We believe this is the case because there are more
options available vs. the true/false questions, but are not unconstrained like
the proof questions, and the prompt gives appropriate context to how ChatGPT
should phrase its solutions to the questions.

##  6\. Threats to Validity

The largest possible threat to the validity of the results is the accuracy of
assigning scores based on the rubric, which was done by only the first and
second authors. We mitigated this threat by having the third author
independently verify the scores’ accuracy, as he has taught the course 8
times.

Another threat comes from a potential low quality of the tested questions. In
order to mitigate this threat, we ensured that the questions came only from
existing ToC resources, such as the course textbook, class notes, pre-class
readings, and former exams; the latter three came from our institution.

##  7\. Recommendations and Future Work

First we give our recommendations for educators who want to either alter their
ToC course to accommodate potential use of LLMs like ChatGPT by students, or
to incorporate assessments utilizing LLMs. Since we have shown that ChatGPT
can effectively pass a ToC course, we recommend keeping assessments that are
closed-resources, such as in-person exams, as the majority of the course
grade. As our results show, an experienced ToC educator can still largely and
safely use questions that have not been asked before that still test the same
fundamental concepts and theorems. However, an essential part of a successful
ToC course is for students to think critically about claims, and to verify
them. In spirit of this, we recommend to include an assignment that involves
asking an LLM to prove a claim from a previous assessment, and then have
students point out every error within the LLM’s output.

As ChatGPT was rarely formal, we recommend requiring students to provide as-
formal-as-reasonable proofs of their claims, especially for reductions such as
undecidable proofs. Although not necessarily new advice, we highly recommend
educators inspect students’ homework submissions for key, specific details in
their proofs. ChatGPT often includes all of the “boilerplate” correctly in
each proof type, but excludes important details, such as how a reduction from
one language to another exactly works. Further, we recommend educators to
require students create non-trivial state diagrams as ChatGPT is unable to
make them unless they are very small, and even these are directly written in
ASCII.

Now we describe future work. Certainly a future work item would be to use the
same method to other LLMs; we predict similar behavior in that proof-type
questions will be done poorly, whereas algorithmic-type questions will be done
well. Of course, the topics we chose are only a small subset of topics within
ToC; one could in principle test ChatGPT against topics such as computational
complexity theory.

In the advent of LLMs, it is ever more important to verify potential proofs of
claims, especially mathematical ones. For future work, one type of question
would be to determine if a given proof is correct, and if not determine where
the fundamental issue(s) is/are; this was one of our Final Exam questions. For
this question, ChatGPT identified the correct proof step that caused the
problem, but had incorrect reasoning as to why it was wrong.

One potentially great project is to build a LLM specifically for ToC content,
especially with explaining concepts, definitions, and breaking down assigned
problems at an undergraduate level without giving away answers. From
experience, students have most issues with starting proofs and often forget
pre-requisite content, namely discrete math. Even though textbooks do provide
such needed content, such as Chapter 0 of Sipser (Sipser, 2013), our students
historically do not read such resources. Further, we would recommend adding
functionality to such an LLM that can walk through some algorithmic process,
such as NFA to DFA conversion. Such a project would require a very large data
set of accurate ToC content for training, but we are not aware of such a
resource if it exists.

##  8\. Conclusion

In this paper we determined whether or not ChatGPT can pass a ToC course. We
accomplished this through two experiments: one based on our course’s exams,
and another based on a large set of questions we developed. Overall, our
experiments show that ChatGPT can “pass” the course with between a B- and a B
average letter grade. ChatGPT does suffer from being largely unable to prove
claims on which it has not been trained, but can solve very standard
exercises.

###### Acknowledgements.

The opinions in the work are solely of the authors, and do not necessarily
reflect those of the U.S. Army, U.S. Army Research Labs, the U.S. Military
Academy, or the Department of Defense.

## References

  * (1)
  * Banerjee et al. (2023) Paramarshi Banerjee, Anurag Srivastava, Donald Adjeroh, Ramana Reddy, and Nima Karimian. 2023.  Understanding ChatGPT: Impact analysis and path forward for teaching Computer science and engineering.  (April 2023).  https://doi.org/10.36227/techrxiv.22639705.v1
  * Dougherty (2024) Ryan E. Dougherty. 2024.  Experiences Using Research Processes in an Undergraduate Theory of Computing Course. In _Proceedings of the 55th ACM Technical Symposium on Computer Science Education V. 1_ (Portland, OR, USA) _(SIGCSE 2024)_. Association for Computing Machinery, New York, NY, USA, 310–316.  https://doi.org/10.1145/3626252.3630849
  * Frieder et al. (2024) Simon Frieder, Luca Pinchetti, Ryan-Rhys Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Petersen, and Julius Berner. 2024.  Mathematical capabilities of chatgpt.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Garey and Johnson (1979) Michael R. Garey and David S. Johnson. 1979.  _Computers and Intractability_.  Freeman and Company.
  * Rodriguez-Echeverría et al. (2024) Roberto Rodriguez-Echeverría, Juan D. Gutiérrez, José M. Conejero, and Álvaro E. Prieto. 2024.  Analysis of ChatGPT Performance in Computer Engineering Exams.  _IEEE Revista Iberoamericana de Tecnologias del Aprendizaje_ (2024), 1–1.  https://doi.org/10.1109/RITA.2024.3381842
  * Sharpe et al. (2024) James S Sharpe, Ryan E Dougherty, and Sarah J Smith. 2024.  Can ChatGPT Pass a CS1 Python Course?  _Journal of Computing Sciences in Colleges_ 39, 8 (2024), 128–142.
  * Sipser (2013) Michael Sipser. 2013.  _Introduction to the Theory of Computation_ (3 ed.).  Course Technology, Boston, MA.
  * Velásquez-Henao et al. (2023) Juan David Velásquez-Henao, Carlos Jaime Franco-Cardona, and Lorena Cadavid-Higuita. 2023.  Prompt Engineering: a methodology for optimizing i nteractions with AI-Language Models in the field of engineering.  (Nov. 2023).  https://doi.org/10.15446/dyna.v90n230.111700