НГУ

Алгоритму дают обычно примерно следующее определение:

У меня вопрос - какое при этом подразумевается определение набора и инструкции? Набор, скорее всего, как-то можно определить через частично упорядоченные множества (помня о том, что алгоритмы бывают параллельными). Но не совсем понимаю - чем здесь отличается понятие инструкции от понятия алгоритма?

Да нет никакого определения алгоритма. Есть попытки формализации: конечные автоматы, формальные грамматики, машина Тьюринга и т.д.

Ваше определение точь-в-точь воспроизводит слова из первой страницы лекций С. Подзорова. Вы до конца дочитайте эти лекции, тогда поймете, что то, что автор назвал определением, -- это не определение, а пояснение.

Да, оттуда я его и списал, был вариант из Википедии, но там оно какое-то рваное получилось.

Можно задать вопрос иначе: всякое ли преобразование является алгоритмом (и наоборот)?

Что значит "преобразование"?

В моём понимании, преобразование - это некоторое отображение одного множества в другое. Множества допустимых входных наборов данных в множество выходных наборов (результатов).

Всё-таки Вам следует дочитать лекции до конца. Тогда Вы узнаете про рекурсивные функции -- еще одну формализацию алгоритма. А Ваши множества будут называться конструктивные пространства.

А также познакомитесь с понятием вычислимая (в интуитивном смысле) функция -- это как раз наше интуитивное представление об алгоритме. Существут тезис Тьюринга о том, что всякая вычислимая (в интуитивном смысле) функция вычислима на машине Тьюринга. Тезис -- потому что доказывать его бессмысленно, ибо вычислимая (в инуитивном смысле) функция не определена точно так же, как не определено общее понятие алгоритма. Поэтому вычислимую в интуитивном смысле функцию формализуют до математически строгого понятия частично рекурсивной функции. Есть теорема о том, что любая чрф вычислима на машине Тьюринга. Естественно, от такой формализации мы кое-что теряем в плане общности, но зато у нас получается строгая математическая теория, а не игра в слова.

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

Верещагин, Шень -- это слишком просто. Если хотите хороших лекций по теории алгоритмов, и даже с оглавлением, то ищите в интернете лекции Березнюка, Когабаева (с оглавлением), Морозова (с оглавлением), Подзорова. У меня они все есть. Могу Вам их как-нибудь отправить.

Пока читаю - такой глупый вопрос: рассматривались ли когда-нибудь модели, в которых такая последовательность символов является не конечной, а счётной? То есть - есть ли какие-то принципиальные ограничения на этот счёт, можно ли там ввести невычислимость и т.п.? Или такая модель вообще не имеет смысла?

Почему же глупый? Я с теорией вычислимости знаком не далее, чем по лекциям. Вот придет Коба и всё объяснит.

Может сам докопаюсь к тому времени


Не знаю пока, но хотелось бы описать конструктивный объект векторами [бесконечномерного] гильбертова пространства. Определение не позволяет

Это Вы процитировали "определение" из самой первой, вводной лекции моего курса.

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

Если хотите строгости --- читайте дальше

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Да читаю я, читаю

Насчёт счётности вот вопрос интересный...

http://www.nsu.ru/education/podzorov/Alg/Course.pdf

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

В принципе можно и бесконечномерные пространства рассматривать. Например, возьмём пространство всех таких (x_0,x_1,...,x_n,...) "векторов" натуральных чисел, которые устроены конструктивно, т.е. для каждого такого вектора существует вычислимая функция f, что f(0)=x_0, f(1)=x_1 и т.д. Тогда пространство всех таких векторов будет счетным, т.к. всех таких функций будет счетное число.

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

Но если не рассматривать "неопределенные векторы", то получится не вполне конструктивное пространство... Т.е. нет такой вычислимой нумерации, с помощью которой можно будет занумеровать все элементы этого пространства. А это уже вопрос интересный. Можно ли на таком пространстве задать функции, метрики, что-нибудь ещё?