2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Невычислимая функция на основе систем диофантовых уравнений
Сообщение13.06.2020, 17:55 


20/04/15
20
Я хочу построить функцию $f:\mathbb{N}\to\mathbb{N}$, которая росла бы быстрее, чем любая вычислимая функция (вроде $Busy Beaver$), используя факт отсутствия алгоритма для разрешения систем диофантовых уравнений.
Значение функции $f(n)$ определяется так: берём все системы диофантовых уравнений с не более, чем $n$ уравнениями не более, чем $n$-й степени, коэффициенты при слагаемых которых по модулю не превышают $n$. Если все такие системы неразрешимы, то $f(n)=0$ (на самом деле таких нет). Иначе, выбираем все системы, которые имеют хотя бы одно решение и для каждой такой системы берём такое решение $(x_1, x_2,.. x_n)$, для которого $\max(|x_i|)$ минимален. Максимальное значение среди всех таких систем и будет значением функции.
Очевидно, функция неразрешима, иначе бы для данной системы можно было бы получить $f(\max(A,B,C))$, где $A$ — количество уравнений, $B$ — степень системы, $C$ — максимальный по модулю коэффициент при одном из множителей.

Вопрос состоит в том, как вычислить или оценить количество систем уравнений для $n$ и какие могут быть идеи для получения первых нескольких значений $f(n)$. Также очень рад буду получить идеи для алгоритма перебора всех систем для заданного $n$.
Будет ли такая функция расти быстрее $Busy Beaver(n)$?

 Профиль  
                  
 
 Re: Невычислимая функция на основе систем диофантовых уравнений
Сообщение14.06.2020, 08:22 
Заслуженный участник


13/12/05
4620
Zeddikus в сообщении #1468709 писал(а):
чем любая вычислимая функция (вроде $Busy Beaver$)

Она же не вычислима!

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


03/06/08
2337
МО
Гипериммунные множества?

 Профиль  
                  
 
 Re: Невычислимая функция на основе систем диофантовых уравнений
Сообщение14.06.2020, 18:53 


20/04/15
20
Padawan в сообщении #1468791 писал(а):
Zeddikus в сообщении #1468709 писал(а):
чем любая вычислимая функция (вроде $Busy Beaver$)

Она же не вычислима!

Да, я это и имел ввиду, выражение в скобках относится ко всему предложению.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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