Связь понятия алгоритма с понятием функции

Таким образом, если изменить машину Тьюринга из самого первого примера так, чтобы умножение чисел записывалось не 111´11, а 0111011, то такая машина реализовывала бы функцию умножения f(x1,x2)=x1´x2. С другой стороны эта же машина реализовывала бы слова вида 01^x101^x20 в слова вида 01^x1´^x20

Понятие об алгоритмической неразрешимоти.Тезис Тьюринга

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