2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 8  След.
 
 Re: понятие вычислимой/невычислимой функции
Сообщение07.04.2021, 16:42 
Заслуженный участник


12/08/10
1608
home-mik в сообщении #1513279 писал(а):
Ведь алгоритм перебора можно, по-моему, для любой функции составить. Другое дело, что он может продолжаться до бесконечности.
Вот в случае отрицательного ответа и будет перебирать бесконечно.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение07.04.2021, 16:51 
Заслуженный участник
Аватара пользователя


28/09/06
10413
Null в сообщении #1513290 писал(а):
Вот в случае отрицательного ответа и будет перебирать бесконечно.

У функции busy beaver нет аргументов, в которых функция не определена. Классическая логика в лице закона исключённого третьего утверждает: "Любая машина Тьюринга либо остановится, либо нет". Это значит, что из любого конечного множества машин Тьюринга можно выбрать такую, которая останавливается и перед этим записывает на ленту максимальное количество символов.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение07.04.2021, 21:39 
Заслуженный участник


27/04/09
28128
epros в сообщении #1513263 писал(а):
Вычислимая функция - это и есть алгоритм.
Надо отметить для ТС, что могут считать и то, что это класс эквивалентности алгоритмов по тому, одинаковые ли они результаты выдают (включая $\bot$) на все входы. Но само это экстенсиональное равенство конечно же в общем случае неразрешимо, так что в конструктивном контексте от него не очень много толку и можно тогда считать сам алгоритмом и функцией. Или можно считать, что совокупность вычислимых [частичных] функций не образует множества, а образует предмножество, которое отличается от множества ровно тем, что от его элементов отодрали равенство и мы не можем больше знать, равны они или нет (но мы можем вводить разные отношения эквивалентности*, превращая предмножество во всяческие множества, между которыми есть натуральные проекции).

()

* Можно подумать, что для установления того, что отношение — эквивалентность — нужно равенство из-за рефлексивности. На деле же мы в таком случае вообще скорее всего будем считать отношением (пред)функцию, которая двум элементам нашего множества сопоставляет предмножество, населённость или ненаселённость которого говорит о том, находятся элементы в отношении или нет (можно считать элементами такого множества всевозможные способы связать два элемента). На языке теории типов мы дальше можем записать требования к отношению $\sim$, чтобы оно было эквивалентностью, как наличие трёх (пред)функций $$\mathrm{refl} \colon (x \colon X) \to (x \sim x)$$ $$\mathrm{sym} \colon (x \colon X) \times (y \colon X) \times (x \sim y) \to (y \sim x)$$ $$\mathrm{trans} \colon (x \colon X) \times (y \colon X) \times (z \colon X) \times (x \sim y) \times (y \sim z) \to (x \sim z).$$ И к примеру чтобы назвать предфункцию $f \colon X \to Y$ функцией из $(X, \sim_X)$ в $(Y, \sim_Y)$, нам надо будет показать, что населён тип $$(x \colon X) \times (y \colon X) \times (x \sim_X y) \to (f(x) \sim_Y f(y)),$$ то есть предоставить алгоритм, переводящий свидетеля равенства элементов в свидетеля равенства их образов при $f$.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 06:16 


08/05/08
593
home-mik в сообщении #1513045 писал(а):
Первый вопрос, который у меня сразу же возникает, это, какой вычислитель имеется ввиду? Любой?

Если любой, то как вообще функция может быть невычислима.

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

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 11:07 


21/03/21
36
epros в сообщении #1513284 писал(а):
home-mik в сообщении #1513279 писал(а):
Ведь алгоритм перебора можно, по-моему, для любой функции составить.

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

Мне в этом примере непонятно вот что: задача вычисления числа Busy Beaver $BB(n)$ для произвольного $n$ и задача подтверждения, что какие-то машины Тьюринга не останавливаются, это две разные задачи или суть одна и та же?

-- 08.04.2021, 11:26 --

ET в сообщении #1513367 писал(а):
home-mik в сообщении #1513045 писал(а):
Первый вопрос, который у меня сразу же возникает, это, какой вычислитель имеется ввиду? Любой?

Если любой, то как вообще функция может быть невычислима.

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

Это пример с диагональным составлением невычислимой функции, насколько я понимаю. Его я тоже, кстати, до конца не пойму. Когда перечисляют все вычислимые функции $f_{1}(n), f_{2}(n), f_{3}(n) ... f_{k}(n)$, а потом вводят $g(n) = f_{n}(n) + 1$. Да, $g(n)$ получается не совпадает ни с одной из этих выше перечисленных вычислимых функций. С другой стороны очевидно, что прибавление единицы не делает ее невычислимой для машины Тьюринга то уж точно. Т.е. она должна быть вычислимой.

Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

И самое главное, как это на практике выглядит? Ведь на практике мы по этому диагональному рецепту невычислимую функцию никогда не составим. Потому что всегда можно будет число вычислимых функций $f_{n}(n)$ дополнить новым экземпляром в том же программном алфавите так, что построенная до этого $g(n)$ будет уже вычислима.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 11:31 
Заслуженный участник
Аватара пользователя


28/09/06
10413
home-mik в сообщении #1513393 писал(а):
Мне в этом примере непонятно вот что: задача вычисления числа Busy Beaver $BB(n)$ для произвольного $n$ и задача подтверждения, что какие-то машины Тьюринга не останавливаются, это две разные задачи или суть одна и та же?

Это одна задача. $\Sigma(n)$ определяется так: Нужно взять все машины Тьюринга с количеством состояний не более $n$ (их конечное количество), стартующие с пустой ленты. Среди тех машин, которые останавливаются, выбрать такую, которая записала на ленту максимальное количество символов (такая машина и называется busy beaver). Вот это количество символов и есть $\Sigma(n)$.

Разумеется, чтобы исключить из рассмотрения те машины, которые никогда не остановятся, нужно убедиться в том, что они действительно никогда не остановятся.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 11:45 


21/03/21
36
epros в сообщении #1513397 писал(а):
Разумеется, чтобы исключить из рассмотрения те машины, которые никогда не остановятся, нужно убедиться в том, что они действительно никогда не остановятся.

И для этого надо их запустить и подождать бесконечное количество времени) Т.е. сама последовательность действий то ясна, просто надо бесконечное количество времени для получения результата. Получается, что алгоритмом считается только такая последовательность действий, которая выдает результат за конечное время, за конечное число шагов.

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

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 11:51 


14/01/11
2916
home-mik в сообщении #1513400 писал(а):
Просто как мне кажется есть принципиальная разница между "я вообще не знаю как к задаче подступиться, т.е. нет алгоритма" и "я знаю как ее решать, но мне для этого времени никогда не хватит, т.е. алгоритм есть, но требует бесконечного числа шагов".

Почему это не знаете, как подступиться? Просто переберите все возможные способы.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:01 
Заслуженный участник
Аватара пользователя


28/09/06
10413
home-mik в сообщении #1513393 писал(а):
Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

Вы что-то неправильно прочитали. Дело не в том, что $f_{n}(n)+1$ не определена для любого $n$, а в том, что нет алгоритма, нумерующего все вычислимые функции, а потому функция, аргументом которой является номер вычислимой функции, не является вычислимой.

home-mik в сообщении #1513393 писал(а):
И самое главное, как это на практике выглядит? Ведь на практике мы по этому диагональному рецепту невычислимую функцию никогда не составим. Потому что всегда можно будет число вычислимых функций $f_{n}(n)$ дополнить новым экземпляром в том же программном алфавите так, что построенная до этого $g(n)$ будет уже вычислима.

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

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:10 


21/03/21
36
Sender в сообщении #1513402 писал(а):
home-mik в сообщении #1513400 писал(а):
Просто как мне кажется есть принципиальная разница между "я вообще не знаю как к задаче подступиться, т.е. нет алгоритма" и "я знаю как ее решать, но мне для этого времени никогда не хватит, т.е. алгоритм есть, но требует бесконечного числа шагов".

Почему это не знаете, как подступиться? Просто переберите все возможные способы.

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

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

Но только тогда возникает вопрос, какая разница между неразрешимостью функции и ее неопределенностью: и то, и другое тогда, выходит, может реализовываться через зацикливание, бесконечное число шагов. Однако неопределенность функции определению алгоритма не противоречит, в отличие от неразрешимости.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:13 


14/01/11
2916
Что вы понимаете под неопределённостью функции?

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:15 
Заслуженный участник
Аватара пользователя


28/09/06
10413
home-mik в сообщении #1513400 писал(а):
И для этого надо их запустить и подождать бесконечное количество времени) Т.е. сама последовательность действий то ясна, просто надо бесконечное количество времени для получения результата.

Это очень странная трактовка. Если алгоритм не останавливается, значит и "результата" у него никакого не будет.

home-mik в сообщении #1513400 писал(а):
Получается, что алгоритмом считается только такая последовательность действий, которая выдает результат за конечное время, за конечное число шагов.

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

home-mik в сообщении #1513400 писал(а):
Просто как мне кажется есть принципиальная разница между "я вообще не знаю как к задаче подступиться, т.е. нет алгоритма" и "я знаю как ее решать, но мне для этого времени никогда не хватит, т.е. алгоритм есть, но требует бесконечного числа шагов".

"Не знаю как" - это Ваша личная проблема. Когда же математик утверждает, что "нет алгоритма", это значит не то, что алгоритма пока не нашли, а то, что его в принципе не может быть.

-- Чт апр 08, 2021 13:23:24 --

home-mik в сообщении #1513405 писал(а):
Другое дело, если определять алгоритм как последовательность действий, выдающая ответ за конечное число шагов.

Бессмысленно говорить о каких-то ответах "за бесконечное количество шагов". Алгоритм - это последовательность операций, всё, точка. Он может иметь точку останова или не иметь. В последнем случае ни о каких "ответах" речи быть не может.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:37 


21/03/21
36
epros в сообщении #1513404 писал(а):
home-mik в сообщении #1513393 писал(а):
Написано, что из этого противоречия следует, что предположение о том, что фукнции $f_{n}(n)$ определены для любого $n$, неверно. Но я честно говоря плохо понимаю, как неопределенность $f_{n}(n)$ для каких-то $n$ помогает снять это противоречие.

Вы что-то неправильно прочитали. Дело не в том, что $f_{n}(n)+1$ не определена для любого $n$, а в том, что нет алгоритма, нумерующего все вычислимые функции, а потому функция, аргументом которой является номер вычислимой функции, не является вычислимой.

Алгоритм перебора то там как раз дается (это из книжки В. Босс "Лекции по математике" том 6):
Цитата:
Как уже отмечалось, процедура вычислений отождествляется с программой работы компьютера, представляющей собой запись алгоритма на некотором языке в некотором алфавите $А$,
$P = a_{1}a_{2}...a_{N}$, все $a_{j} \in A$ (1.2)
Программа применяется к различным входным словам. Если входные и выходные данные кодируются числами, программа
определяет вычислимую функцию.

Запись программы вычислений в виде (1.2) позволяет все вычислимые функции перенумеровать,
$f_{1}(n), ..., f_{k}(n), ...$ (1.3)
Сначала перечисляются все программы из одной буквы, потом из двух, потом из трех и так далее.

Ну а дальше само утверждение:
Цитата:
1.5.1. Теорема. Любая попытка ввести понятие вычислимой
функции $f(n)$ так, чтобы она была определена при любом $n$, — неразумна.

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

Дальше пояснение идет:
Цитата:
Если какие-то функции в перечислении (1.3) определены не при всех $n$, конструкция $g(n) = f_{n}(n) + 1$ к противоречию не приводит. (?)

Формулировка теоремы 1.5.1, конечно, слегка зашкаливает, но здесь важно заострить внимание. Определение вычислимой
функции $f(n)$ при любом $n$ — принципиально обречено на провал. Или получаются слишком узкие классы функций, дискредитирующие понятие вычислимости, или какие-то $f(n)$ перестают вычисляться. А попытка доопределить $f(n)$ «силовым методом» не проходит, иначе получается сказка про белого бычка — возврат к теореме 1.5.1, и — по тому же кругу.

Из пояснения я понял чуть больше, чем ни хрена) Так что вполне возможно, что я что-то неправильно домыслил.

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 12:42 
Заслуженный участник
Аватара пользователя


28/09/06
10413
home-mik в сообщении #1513405 писал(а):
алгоритм перебора то есть всегда. Просто он бесконечным может быть.

Ещё раз: Для решения задачи доказательства того, что некий алгоритм не останавливается, не существует алгоритма. Не в том смысле, что его пока не нашли, а в том смысле, что его в принципе не может быть.

-- Чт апр 08, 2021 13:54:14 --

home-mik в сообщении #1513414 писал(а):
Алгоритм перебора то там как раз дается (это из книжки В. Босс "Лекции по математике" том 6):

Дело в том, что не всякая последовательность символов является кодом алгоритма. Соответственно, если мы пронумеруем последовательности символов, то номера кодов алгоритмов среди них окажутся только неким подмножеством. А не всякое подмножество натуральных чисел является рекурсивным (т.е. определяемым с помощью алгоритма).

 Профиль  
                  
 
 Re: понятие вычислимой/невычислимой функции
Сообщение08.04.2021, 13:12 


21/03/21
36
Sender в сообщении #1513406 писал(а):
Что вы понимаете под неопределённостью функции?

Да вот хотя бы по определению из книжки Шеня:
Цитата:
если $f(n)$ не определено, то алгоритм $A$ не останавливается на входе $n$

Можно было бы изменить определение, сказав так: "если $f(n)$ не определено, то либо алгоритм $A$ не останавливается, либо останавливается, но ничего не печатает


-- 08.04.2021, 13:22 --

epros в сообщении #1513415 писал(а):
Дело в том, что не всякая последовательность символов является кодом алгоритма. Соответственно, если мы пронумеруем последовательности символов, то номера кодов алгоритмов среди них окажутся только неким подмножеством. А не всякое подмножество натуральных чисел является рекурсивным (т.е. определяемым с помощью алгоритма).

Насколько я знаю, фильтрация кодов на предмет синтаксически правильных делается лексическим анализатором, т.е. вроде вполне определенным алгоритмом.

Примерно то же кстати и В. Босс пишет в качестве прелюдии к этой теореме 1.5.1:
Цитата:
Неопределенность некоторых вычислимых функций заключается не только в ошибочных программах, приводящих к зависанию компьютера. Отсеять «мусор» из (1.3) можно введением грамматического фильтра, способного оставить в последовательности (1.3) только те тексты, которые действительно являются программами. Пробелов нумерации легко избежать, нумеруя после фильтрации. Однако никакие меры не могут предотвратить зацикливание некоторых программ на некоторых входах, — и любые усилия в этом направлении бессмысленны.

Ну вот последнего утверждения как и следующей из него теоремы 1.5.1 я как раз и не пойму.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 112 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 8  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group