Упрощенное доказательство распознаваемости симметричности слов в реальное время на машинах Тьюринга

Приводится сравнительно короткое доказательство распознаваемости симметричности слов в реальное время на многоленточных машинах Тьюринга. Оно основано на основных идеях первоначального доказательства, принадлежащего автору, и на идее Ц. Галила использовать для упрощения доказательства алгорифм Фишера–Пэтерсона для нахождения всех симметричных концов слова в линейное время. Библ. 7 назв.