1. Все предложенные варианты формализации приводят к одному и тому же понятию вычислимой функции (алгоритма).
2. Для многих интуит. вычисл. функций были найдены программы вычисл. эти функции.
3. Любую программу в одной модели мы можем записать программой из другой модели.
2. Для многих интуит. вычисл. функций были найдены программы вычисл. эти функции.
3. Любую программу в одной модели мы можем записать программой из другой модели.
Тезис Чёрча-Тьюринга.
Всякая "интуитивно" вычислимая функция вычислима в формальном смысле.
Всякая "интуитивно" вычислимая функция вычислима в формальном смысле.
В рамках всей математики есть тезис - люди не зная правил игры, играют по правилам.
Понятия алгоритма:
Всякий алгоритм может принимать на вход какие-то данные.
Всякий алгоритм может давать на что-то выход.
Вход и выход конечны в символьном виде.
Всякий алгоритм - конечный текст.
Есть синтаксис (правила написания программы) и семантика (значение программы).
Алгоритм - пошаговый процесс. И каждый следующий шаг однозначно определён текущим положением.
Всякий алгоритм может принимать на вход какие-то данные.
Всякий алгоритм может давать на что-то выход.
Вход и выход конечны в символьном виде.
Всякий алгоритм - конечный текст.
Есть синтаксис (правила написания программы) и семантика (значение программы).
Алгоритм - пошаговый процесс. И каждый следующий шаг однозначно определён текущим положением.
\Sigma - алфавит.
f: \Sigma* -> \Sigma* - функция.
\Sigma* - множество всех конечных слов в алфавите \Sigma.
Мы будем рассматривать функции f: \N -> \N (функции от одной переменной).
И функции f: \N^k -> \N (функции от k переменных).
В нашем курсе \N = {0, 1, 2, ...}.
f: \Sigma* -> \Sigma* - функция.
\Sigma* - множество всех конечных слов в алфавите \Sigma.
Мы будем рассматривать функции f: \N -> \N (функции от одной переменной).
И функции f: \N^k -> \N (функции от k переменных).
В нашем курсе \N = {0, 1, 2, ...}.