Background

Think of pointers as just a separate data type. They have their own storage requirements -- such as their size -- they occupy 8 bytes on a x86_64 platform. This is the case of void pointers void*.

In those 8 bytes the information stored is the memory address of another piece of data.

The thing about pointers is that since they "point" to another piece of data, it's useful to know what type that data is too so you can correctly handle it (know its size, and structure).

In stead of having their own data type name such as pointer they compose their name based on the data type they refer to such as int* a pointer to an integer. If you want a plain pointer without type information attached to it you have the option of using void*.

So basically each pointer (to int, to char, to double) is just a void* (same size, same use) but the compiler knows the data being pointed to is of type int and allows you to handle it accordingly.

/**
 *  Create a new pointer to an unknown type.
 */
void* data;

/**
 *  Allocate some memory for it using malloc
 *  and tell your pointer to point to this new
 *  memory address (because malloc returns void*).
 *  I've allocated 8 bytes (char is one byte).
 */
data = malloc(sizeof(char)*8);

/**
 *  Use the pointer as a double by casting it
 *  and passing it to functions.
 */
double* p = (double* )data;
p = 20.5;
pow((double* )data, 2);

Pointer to array

If you have an array of values (let's say integers) somewhere in memory, a pointer to it is one variable containing its address.

You can access this array of values by first dereferencing the pointer and then operating some work on the array and its values.

/**
 *  Create an array containing integers.
 */
int array[30];
array[0] = 0;
array[1] = 1;
...
array[29] = 29;

/**
 *  Create a pointer to an array.
 */
int (*pointer)[30];

/**
 *  Tell the pointer where the data is.
 */
pointer = &array;

/**
 *  Access the data through the pointer.
 */
(*pointer)[1] = 999;

/**
 *  Print the data through the array.
 *  ...and notice the output.
 */
printf("%d", array[1]);

Array of pointers

If you have an array of pointers to values, the entire array of pointers is one variable and each pointer in the array refers to somewhere else in the memory where a value is located.

You can access this array and the pointers inside it without dereferencing it but in order to reach a certain value from it you will have to dereference one of the pointers inside the array.

/**
 *  Create an array containing pointers to integers.
 */
int *array_of_pointers[30];
array_of_pointers[0] = 0;
array_of_pointers[1] = 1;
...
array_of_pointers[29] = 29;

Use the cdecl program, as suggested by K&R.

$ cdecl
Type `help' or `?' for help
cdecl> explain int* arr1[8];
declare arr1 as array 8 of pointer to int
cdecl> explain int (*arr2)[8]
declare arr2 as pointer to array 8 of int
cdecl> explain int *(arr3[8])
declare arr3 as array 8 of pointer to int
cdecl>

It works the other way too.

cdecl> declare x as pointer to function(void) returning pointer to float
float *(*x)(void )

First,

I also have a rough understanding that arrays themselves are pointers, and that arr[p] evaluates to (arr + p * sizeof(data_type_of_arr)) where the name arr decays to the pointer to the first element of arr.

This isn't strictly correct. Arrays are not pointers. Under most circumstances, expressions of array type will be converted ("decay") to expressions of pointer type and the value of the expression will be the address of the first element of the array. That pointer value is computed as necessary and isn't stored anywhere.

Exceptions to the decay rule occur when the array expression is the operand of the sizeof, _Alignof, or unary & operators, or is a string literal used to initialize a character array in a declaration.

Having said all that, ptr_to_arr has pointer type, not array type - it will not "decay" to int **.

Given the declaration

T arr[N];

the following are true:

 Expression        Type            Decays to            Equivalent expression
 ----------        ----            ---------            ---------------------
        arr        T [N]           T *                  &arr[0]
       *arr        T               n/a                  arr[0]
     arr[i]        T               n/a                  n/a
       &arr        T (*)[N]        n/a                  n/a

The expressions arr, &arr[0], and &arr all yield the same value (modulo any differences in representation between types). arr and &arr[0] have the same type, "pointer to T" (T *), while &arr has type "pointer to N-element array of T" (T (*)[N]).

If you replace T with pointer type P *, such that the declaration is now

P *arr[N];

you get the following:

 Expression        Type            Decays to            Equivalent expression
 ----------        ----            ---------            ---------------------
        arr        P *[N]          P **                 &arr[0]
       *arr        P *             n/a                  arr[0]
     arr[i]        P *             n/a                  n/a
       &arr        P *(*)[N]       n/a                  n/a

So given your declarations, it would be more correct to write something like this:

int arr[x];
int *p1 = arr;         // the expression arr "decays" to int *

int *arr_of_ptr[x];
int **p2 = arr_of_ptr; // the expression arr_of_ptr "decays" to int **

/**
 * In the following declarations, the array expressions are operands
 * of the unary & operator, so the decay rule doesn't apply.
 */
int (*ptr_to_arr)[x] = &arr;
int *(*ptr_to_arr_of_ptr)[x] = &arr_of_ptr;

Again, ptr_to_arr and ptr_to_arr_of_ptr are pointers, not arrays, and do not decay to a different pointer type.

EDIT

From the comments:

Can I just hand-wavily explain it as： an array of pointers has a name that can decay to a pointer,

Yeah, -ish, just be aware that it is hand-wavey and not really accurate (which is shown by example below). If you are a first-year student, your institution isn't doing you any favors by making you deal with C this early. While it is the substrate upon which most of the modern computing ecosystem is built, it is an awful teaching language. Awful. Yes, it's a small language, but aspects of it are deeply unintuitive and confusing, and the interplay between arrays and pointers is one of those aspects.

an array of pointers has a name that can decay to a pointer, but a pointer to an array, even when dereferenced, does not give a give me something that decays to a pointer?

Actually...

If ptr_to_arr has type int (*)[x], then the expression *ptr_to_arr would have type int [x], which would decay to int *. The expression *ptr_to_arr_of_ptr would have type int *[x], which would decay to int **. This is why I keep using the term "expression of array type" when talking about the decay rule, rather than just the name of the array.

Something I have left out of my explanations until now - why do array expressions decay to pointers? What's the reason for this incredibly confusing behavior?

C didn't spring fully-formed from the brain of Dennis Ritchie - it was derived from an earlier language named B (which was derived from BCPL, which was derived from CPL, etc.)¹. B was a "typeless" language, where data was simply a sequence of words or "cells". Memory was modeled as a linear array of "cells". When you declared an N-element array in B, such as

auto arr[N];

the compiler would set aside all the cells necessary for the array elements, plus an extra cell that would store the numerical offset (basically, a pointer) to the first element of the array, and that cell would be bound to the variable arr:

     +---+
arr: | +-+-----------+
     +---+           |
      ...            |
     +---+           |
     |   | arr[0] <--+
     +---+
     |   | arr[1]
     +---+
      ...
     +---+
     |   | arr[N-1]
     +---+
      

To index into the array, you'd offset i cells from the location stored in arr and dereference the result. IOW, a[i] was exactly equivalent to *(a + i).

When Ritchie was developing the C language, he wanted to keep B's array semantics (a[i] is still exactly equivalent to *(a + i)), but for various reasons he didn't want to store that pointer to the first element. So, he got rid of it entirely. Now, when you declare an array in C, such as

int arr[N];

the only storage set aside is for the array elements themselves:

+---+
|   | arr[0]
+---+
|   | arr[1]
+---+
 ... 
+---+ 
|   | arr[N-1]
+---+

There is no separate object arr which stores a pointer to the first element (which is part of why array expressions cannot be the target of an assignment - there's nothing to assign to). Instead, that pointer value is computed as necessary when you need to subscript into the array.

This same principal holds for multi-dimensional arrays as well. Assume the following:

int a[2][2] = { { 1, 2 }, { 3, 4 } };

What you get in memory is the following:

   Viewed as int             Viewed as int [2]
   +---+                     +---+
a: | 1 | a[0][0]           a:| 1 | a[0]
   +---+                     + - +
   | 2 | a[0][1]             | 2 |
   +---+                     +---+
   | 3 | a[1][0]             | 3 | a[1]
   +---+                     + - +
   | 4 | a[1][1]             | 4 |
   +---+                     +---+

On the left we view it as a sequence of int, while on the right we view it as a sequence of int [2].

Each a[i] has type int [2], which decays to int *. The expression a itself decays from type int [2][2] to int (*)[2] (not int **).

The expression a[i][j] is exactly equivalent to *(a[i] + j), which is equivalent to *( *(a + i) + j ).