2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 тема в заглавии
Сообщение03.07.2008, 14:22 
Профессор Снэйп писал(а):
Цитата:
Каждое рекурсивно перечислимое отношение задаётся на $\mathbb{N}$ экзистенциальной формулой языка элементарной арифметики.


Спасибо. Если у Вас уже есть рекурсивно-перечислимое отношение для всех простых чисел, то все остальные рассуждения нужны, для того чтобы кто нибудь спросил.
Цитата:
Вас что интересует: определение многочлена или "неожиданный" факт, гласящий, что у ненулевого многочлена от нескольких переменных нулей может быть бесконечно много?

Да. И то и другое "и можно в одну посудину". С уважением,

 
 
 
 Re: тема в заглавии
Сообщение03.07.2008, 15:06 
Аватара пользователя
hurtsy писал(а):
Если у Вас уже есть рекурсивно-перечислимое отношение для всех простых чисел, то все остальные рассуждения нужны...


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

hurtsy писал(а):
Да. И то и другое "и можно в одну посудину". С уважением,


1) Многочленом с коэффициентами из коммутативного кольца $A$ и переменными из множества $S$ называется элемент моноидной алгебры $A[\mathbb{N}\langle S \rangle]$.

2) Рассмотрите многочлен $f(x,y) = x-y$. Все пары $\langle x,x \rangle$ для $x \in \mathbb{N}$ будут его корнями, не так ли?

Добавлено спустя 19 минут 42 секунды:

ddn писал(а):
Я знаю совсем другую формулировку...


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

Единственное, что могу сказать: решение 10-ой проблемы Гильберта из этой формулировки действительно следует. А из Вашей --- нет, не вижу, как могло бы следовать. А ведь Матиясевич прославился именно тем, что сделал завершающий шаг в решении 10-ой проблемы Гильберта!

 
 
 
 тема в заглавии
Сообщение03.07.2008, 15:31 
Профессору Снэйп.

Большое спасибо. Было весело. Ваши рассуждения понятны. Я считал, что дискусия идет на тему арифметических простых чисел, а многочлены имеются в виду от одной переменной. Но что Вы можете посоветовать если требуется найти штук 10 простых чисел с например 2008 десятичними знаками. С уважением,

 
 
 
 Re: тема в заглавии
Сообщение03.07.2008, 15:33 
Аватара пользователя
hurtsy писал(а):
Я считал, что дискусия идет на тему арифметических простых чисел, а многочлены имеются в виду от одной переменной.


Угу. Если написано $f(x_1, \ldots, x_k,y)$, то $f$ --- многочлен от одной переменной, и никак иначе :)

С термином "арифметические простые числа" сталкиваюсь первый раз. Они что, бывают "не арифметические"?

 
 
 
 
Сообщение03.07.2008, 21:10 
hurtsy писал(а):
Я имею в виду, что проверка простоты больших простых чисел не производится прямым перебором возможных делителей. Используемые методы (probabalistic algorithm вероятностный алгоритм).

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

 
 
 
 
Сообщение03.07.2008, 21:53 
Аватара пользователя
naiv1 писал(а):
Означает ли это, что число, прошедшее успешную проверку на простоту этими вероятностными методами, может быть на самом деле составным?
Означает. Например, в тесте Миллера — Рабина после получения k проверок и получения k случайных "свидетелей простоты" проверяемого числа выдается ответ, что проверяемое число является простым с вероятностью не менее, чем \[
1 - \frac{1}{{2^{2k} }}
\]. И такой ответ всех обычно устраивает :shock:
Вот неплохая книга с описанием подобного рода алгоритмов:
Василенко О.Н. — Теоретико-числовые алгоритмы в криптографии

 
 
 
 
Сообщение06.07.2008, 13:09 
Я форму исправил - спасибо за критику формул.
Как насчет содержания?

// обсуждение алгоритма Конвея вынесено в соответствующую тему // maxal

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 11:58 
Про полином Матиясевича отсюда: ссылка
Изображение

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

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 12:28 
vovkaturov в сообщении #544129 писал(а):
Правильно ли я понимаю, что для практического получения простых чисел этот полином бесполезен?
Довольно трудно поверить в то, что он полезен.
vovkaturov в сообщении #544129 писал(а):
А вероятность получения положительного значения путём случайной генерации переменных исчезающе мала?
Я не пробовал, но скорее всего да. Можно попытаться пробежать по единичному кубу хотя бы ради интереса...

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 15:20 
Sonic86 писал(а):
Можно попытаться пробежать по единичному кубу хотя бы ради интереса...

В этой формуле из статьи точно нет ошибок? Там же в скобках единица минус одни квадраты, как этот полином вообще может положительные значения принимать?

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 15:28 
vovkaturov в сообщении #544201 писал(а):
Там же в скобках единица минус одни квадраты, как этот полином вообще может положительные значения принимать?
Может, но только если все квадраты будут нулевыми.

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 15:41 
nnosipov писал(а):
Может, но только если все квадраты будут нулевыми.
А, понятно. То есть эта вещь практически бесполезная. Надо приравнивать квадраты к нулю и решать систему нелинейных уравнений. Это нереально.

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 17:03 
vovkaturov в сообщении #544207 писал(а):
nnosipov писал(а):
Может, но только если все квадраты будут нулевыми.
А, понятно. То есть эта вещь практически бесполезная. Надо приравнивать квадраты к нулю и решать систему нелинейных уравнений. Это нереально.

Тема начиналась с вопроса-существует ли формула простых чисел. Существует и ни одна http://ega-math.narod.ru/Quant/Primes.htm
Вопрос использования этих формул тоже интересен, но уже другой!

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 18:39 
Sonic86 в сообщении #544138 писал(а):
vovkaturov в сообщении #544129 писал(а):
Правильно ли я понимаю, что для практического получения простых чисел этот полином бесполезен?
Довольно трудно поверить в то, что он полезен.
vovkaturov в сообщении #544129 писал(а):
А вероятность получения положительного значения путём случайной генерации переменных исчезающе мала?
Я не пробовал, но скорее всего да. Можно попытаться пробежать по единичному кубу хотя бы ради интереса...

Если мне память не изменяет то этот многочлен давно сократили то-ли до 12 то-ли до8 знаков. А сам автор пришел к выводу что несушествует не каких формул для простых чисел кроме как сплошного перебора.

 
 
 
 Re: Формула для n-ного простого числа
Сообщение01.03.2012, 21:40 
serega57 в сообщении #544300 писал(а):
Если мне память не изменяет то этот многочлен давно сократили то-ли до 12 то-ли до8 знаков. А сам автор пришел к выводу что несушествует не каких формул для простых чисел кроме как сплошного перебора.
Вообще как бы между формулами и алгоритмами особой разницы нет. Алгоритмов генерации простых и их проверки - множество. Можно посмотреть в том же Василенко.

 
 
 [ Сообщений: 63 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group