Убедитесь, что в течение всей симуляции ТМ не происходит никаких распределений.

Предварительно выделяйте один глобальный массив при запуске программы, который достаточно велик для любого состояния ленты (например, элементов 10^8). Сначала поместите машину в начало этого ленточного массива. Сохраните сегмент [0; R] всех ячеек, которые были посещены текущей симуляцией машины: это позволяет избежать очистки всего массива лент при запуске новой симуляции.

Используйте наименьший целочисленный тип для элементов ленты, которого достаточно (например, используйте unsigned char, если в алфавите наверняка меньше 256 символов). Возможно, вы даже можете переключиться на наборы битов, если алфавит очень маленький. Это уменьшает объем памяти и повышает производительность кэша/ОЗУ.

Избегайте использования общих целочисленных делений в самом внутреннем цикле (они медленные), используйте только деления на степень двойки (они превращаются в битовые сдвиги). В качестве окончательной оптимизации можно попробовать удалить все ветки из самого внутреннего цикла (для этого есть разные хитрые приемы).

Вот еще один ответ с более алгоритмическими подходами.

Моделирование по блокам

Поскольку у вас крошечный алфавит и небольшое количество состояний, вы можете ускорить симуляцию, обрабатывая куски ленты одновременно. Это связано с известной теоремой об ускорении, хотя я предлагаю немного другой метод.

Разделите ленту на блоки по 8 символов в каждом. Каждый такой блок может быть представлен 16-битным числом (по 2 бита на символ). Теперь представьте, что автомат находится либо на первом, либо на последнем символе блока. Тогда его дальнейшее поведение зависит только от его начального состояния и начального значения на блоке, пока ТМ не выйдет из блока (либо влево, либо вправо). Мы можем предварительно вычислить результат для всех комбинаций (значение блока + состояние + конец) или, возможно, лениво вычислить их во время моделирования.

Этот метод может имитировать около 8 шагов одновременно, хотя, если вам не повезет, он может выполнять только один шаг за итерацию (движение вперед и назад по границе блока). Вот пример кода:

//R = table[s][e][V] --- outcome for TM which:
//  starts in state s
//  runs on a tape block with initial contents V
//  starts on the (e = 0: leftmost, e = 1: rightmost) char of the block
//The value R is a bitmask encoding:
//  0..15 bits: the new value of the block
//  16..17 bits: the new state
//  18 bit: TM moved to the (0: left, 1: right) of the block
//  ??encode number of steps taken??
uint32_t table[2][2][1<<16];

//contents of the tape (grouped in 8-character blocks)
uint16_t tape[...];

int pos = 0;    //index of current block
int end = 0;    //TM is currently located at (0: start, 1: end) of the block
int state = 0;  //current state
while (state != 2) {
  //take the outcome of simulation on the current block
  uint32_t res = table[state][end][tape[pos]];
  //decode it into parts
  uint16_t newValue = res & 0xFFFFU;
  int newState = (res >> 16) & 3U;
  int move = (res >> 18);
  //write new contents to the tape
  tape[pos] = newValue;
  //switch to the new state
  state = newState;
  //move to the neighboring block
  pos += (2*move-1);
  end = !move;
  //avoid getting out of tape on the left
  if (pos < 0)
      pos = 0, move = 0;
}

Проблема с остановкой

В комментарии говорится, что симуляция ТМ должна либо завершиться очень рано, либо выполнить все шаги до предопределенного огромного предела. Поскольку вы собираетесь моделировать множество машин Тьюринга, возможно, стоит потратить некоторое время на решение проблемы остановки.

Изменять

int move = data % 2;

To

int move = data & 1;

Один — деление, другой — битовая маска, оба должны давать 0 или 1 в младшем бите. Вы можете сделать это в любое время, когда у вас есть % степени двойки.

Вы также устанавливаете

cell = tape[head];
data = TM[current_state][cell]; 
int move = data % 2;
int write = (data % 10) % 3;
current_state = data / 10;

Каждый шаг, независимо от того, изменилась ли лента [голова] и даже на ветвях, где вы вообще не обращаетесь к этим значениям. Внимательно следите за тем, какие ветки используют какие данные, и обновляйте данные только по мере необходимости. Смотрите сразу после этого вы пишете:

    if(current_state == halt_state) {
        // This highlights the last place that is written to in the tape
        tape[head] = 4;
        vector<int> res = shorten_tape(tape);
        res.push_back(i+1);
        return res;
    }

^ Этот код не ссылается на «перемещение» или «запись», поэтому вы можете поместить вычисление для «переместить»/«записать» после него и вычислить их только в том случае, если current_state != halt_state

Также истинная ветвь оператора if является оптимизированной ветвью. Проверив состояние не остановки и поместив условие остановки в ветвь else, вы можете немного улучшить предсказание ветвления ЦП.