Modus,
Прочитал Ваш длинный интересный пост.
Спасибо. Я старался сделать пост понятным.
У меня как у дилетанта в математике процедура диагонализации вызывает недоверие и ощущение, что вешают лапшу на уши.
Такое бывает…
Не останавливаясь на Ваших рассуждениях об алгоритмах и «функция работает неправильно» (если было бы время можно было бы поспорить и об этом) перейду к главному.
Пардон... Но это не мои рассуждения, я просто их популяризовал – сделал доступными для форумчан. Это обычная, и почти банальное упражнение- теорема математической логики и теории алгоритмов, доказывается наверное в любом учебнике. Просто не всем доступен этот язык.
Что такое хорошо определена? Чем это отличается от определена плохо?
«Хорошо определена» - означает, что указан явным образом способ, как по каждой паре натуральных чисел получить другое натуральное число соответствующее ей.
- Вы при описании функции ссылаетесь на некий список функций.
А его ещё нет.
Его ещё только предстоит построить.
Это обычное устойчивое выражение. «Список» - означает, что существует биекция N на множество функций арифметики. Если такой биекции не существует, то и доказывыть вообще нечего – результат теоремы следует просто автоматически. Потому мы и предполагаем обратное - что всякую функцию можно запрограммировать, а потом показываем, что множество всех функций какого либо языка можно занумеровать (см. метод лексикографической сортировки) т.е. построить биекцию между N и функциями нашего языка. (тут надо бы добавить –«не просто занумеровать, а «эффективно занумеровать» - но на том уровне на котором мы пока разговариваем – этого вполне достаточно)
И если будет построен хотя бы один список, из него можно получить бесконечное множество альтернативных списков.
Нам начхать какой список мы возьмем, все списки равномощны друг другу и являют собой одно и тоже множество состоящее из одних и тех же элементов, они отличаются только порядком.
Но списков – ровно континуум, и каждый список дает по крайней мере одну функцию, которая не может быть записана на нашем языке, а потому, всех функций которые не могут быть записаны – тоже не менее континуума. А вот всего того, что можно написать не только на каком-то конкретном языке, но и вообще на всех языках, уже существующих и ещё не созданных – счетно. Но континуум и счетное множество не равномощны. А потому, существует подножество функций, равномощное R и такое, что ни одна из них не может быть запрограммирована никогда.(последние два тезиса предлагая Вам в качестве самостоятельного упражнения)
- Вы пишете, что «она действует из N*N в N».
Но, по-моему, это не так.
Оно не может быть «не так» - поскольку явным образом указано, «что именно» и «как».
У Вас на входе ещё список функций. «H(k,x)=funcn_k(x).»
Для разных списков funcn_ выдаст вам разные H.
Это то и замечательно. Отсюда и следует, что раз разных H –у нас не менее континуума, то и разных G – у нас тоже не менее континуума. И не одна из них не может быть запрограммирована.
( Кстати Вам буква «G» – имя никакого ученого случайно не напоминает?).
- То, что Вы описали больше похоже на систему уравнений, а не на определение функции.
Вот для этого случая я заранее привел определение функции, Вам остается проверить, что именно это и имеет место.
Но если мы, например, попытаемся определить функцию таким образом f(x)^2 == -1, никто же будет говорить, что функция хорошо определена, просто она невыразима.
Как это «невыразима»? Функция ваша – определена плохо, потому, что не указана область её определения и область значения, и неуказан способ, как по каждому элементу их области определения получить некоторый элемент из области значения. Но сама функция –выразима в том смысле, что существует такой х, что х*х=-1, посему если в качестве области определения и значения значения взять поле С, то эта функция будет как осмысленна так и "выразима" так и хорошо определена.
Но вообще, то о чем я говорю в той теореме, когда говорю о выразимости - несколько больше, чем то что предпологаете видимо Вы.
Нет. Скажут, что система уравнений несовместна, что решения не существует, что такой функции не существует. Почему же для Вашей функции должен быть иной подход?
Какая система уравнений? Это Вас куда –то уже не туда понесло извините…
- А даже если бы уже и был готовый всеобъемлющий список.. Ваша система уравнений выглядела таким бы образом.
У нас и в помине нет никакой системы уравнений.
G(1) == A(1)+1, G(2) == B(2)+1 …– пока хорошо, но как только мы доходим до определённой точки – G(6) == F(6)+1, G(7) == G(7)+1 (!) - как видим, что если бесконечность не входит в наши числа, то система уравнений несовместна. Значит и функции такой G – нет.
Этого я, увы, вообще не понял.
Заранее спасибо за ответ.
Пожалуйста. Если есть вопросы – рад помочь интересующемуся человеку. (только я завтра улетаю в Москву, так шо сильно не торопитесь с вопросами)
:wink:
