|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | (покажи всички)
Тема
|
Изчислимост
|
|
Автор |
Numberous (минаващ) |
Публикувано | 25.03.08 15:52 |
|
пи=корен квадратен 6(1+1/4+1/9+1/16+1/25...)
пи= 4( 1-1/3+1/5-1/7+1/9-1/11+...)
пи=2х2/1х2/3х4/3х4/5х6/7х8/9...
е=1+1/1+1/1х2+1/1х2х3+1/1х2х3х4+...
е^z=1+z/1+z^2/1x2+z^3/1x2x3+z^4/1x2x3x4+...
Някой може ли да ми каже как са изведени тези формули?
Какво означава някое реално число да е неизчислимо?
Може ли винаги за всяка редица да се измисли формула, генерираща последователно членовете и? Ако да, как се съставят такива формули?
А може ли някой да ми обясни какво е ламбда анализ на Чърч (ама възможно най-простичко)?
Ne vsi4ko e vuzmojno, za6toto nqkoi ne6ta sa napulno sigurni
| |
Тема
|
Re: Изчислимост
[re: Numberous]
|
|
Автор | Nedev (Нерегистриран) |
Публикувано | 25.03.08 16:31 |
|
В повечето формули които си дал няма неква особена хитрост.
Първата се доказва по много начини, има включително изцяло геометрично доказателство (правили сме го в училище едно време).
Втората се извежда с ред на Тейлър на ф-ята arctan(x).
Третата (формула на Уолис) се извежда например тук:
Четвъртата и петата следват от Тейлър за е^х
| |
Тема
|
Re: Изчислимост
[re: Numberous]
|
|
Автор | 3зз (Нерегистриран) |
Публикувано | 25.03.08 21:22 |
|
Тази система "Lambda Calculus" е била замислена от Чърч да се ползва за пресмятане и доказване на твърдения. Първоначалната му система се оказва противоречива (доказано от 2-ма негови аспиранти Клини и Росер), но после Чърч я оправя. Както и да е, доказано е че системата на Чърч е еквивалентна на други концепции, като машината на Тюринг (доказал го е самия Тюринг), на продукционната система на Пост, на рекурсивните функции на Гьодел, на системата на Марков. Тази еквивалентност е накарала по-късно Чърч да постулира своята "Хипотеза на Чърч".
Това е от раздел "теория на рекурсията", под-раздел на математическата логика.
Има доста пълна и изчерпателна книга по Ламбда Смятане:
В народната библиотека или ЦИНТИ има руски превод.
Книгата на Барендрегт е доста тежка за четене - за специалисти. Не ти я препоръчвам. Ако искаш да започнеш с теория на рекурсията, по-добре вземи някоя книга за начинаещи, като тази например:
Също има превод на руски в нашите библиотеки.
В тази книга няма никакво ламбда смятане, но се разказва за същите работи, с други средства. Изобщо езика на ламбда смятането е останал малко в страни; предпочита се модела Тюринг, което е нещо като стандард в теория на рекурсията.
| |
Тема
|
Re: Изчислимост
[re: 3зз]
|
|
Автор |
Numberous (минаващ) |
Публикувано | 26.03.08 14:44 |
|
А знаеш ли, дали за всяка числова редица може да се състави формула, генерираща последователно елементите и?
Ne vsi4ko e vuzmojno, za6toto nqkoi ne6ta sa napulno sigurni
| |
Тема
|
Re: Изчислимост
[re: Numberous]
|
|
Автор | Zzz (Нерегистриран) |
Публикувано | 26.03.08 17:30 |
|
Разбира се че може. Може да се състави ламбда-израз, да се построи машина на Тюринг, или да се напише компютърна програма, която изброява елементите на редицата.
Нали според така наречения "Тезис на Чърч" който ти спомена на друго място, това което изобщо може да сметне човек (да изброи, калкулира, да изпише..) може да го направи машимата на Тюринг, ламбда-смятането, и т.н. Даже повече -- човек е смъртен и бавно смята. Една машина на Тюринг (или компютър) може да работо 1000 години и да изписва поредния знак от числото ПИ. Самия ред е безкраен и никога няма да спре да се изписва .. но важното е че машината може да достигне до които и да е знак... ако трябва да работи и 2000 години :)
(което не значи, чв няма неразрешими проблеми; в теория на рекурсията се доказват много теореми за не-разрешими проблеми - нито машината на Тщринг нито човек е в състояние да ги реши; например логиката от 1-ви порядък е неразрешима, както показва и теоремата на Гьодел - т.е. има достатъчно силни теории в които има верни твърдения но не-доказуеми).
| |
Тема
|
Re: Изчислимост -- оопппс
[re: Zzz]
|
|
Автор | ззз (Нерегистриран) |
Публикувано | 26.03.08 17:56 |
|
Оопс.. не обърнах внимание на думите <за всяка редица>; имах в предвид всяака числова редица която можем да дафинираме <конструктивно> - за нея може да се построи ламбда израз.
В общия случай не може.
Пример:
-- Може да се напише програма (или ламбда израз) който да изброява и исписва всички твърдения в теория на числата ф1, ф2, ф3, ... Това е сигурно че може.
-- Обаче не може да напишам програма която изпива например такъв ред: <ф1,0>, <Ф2,1>, <ф3, 1>, <ф4,0>,.... т.е. да изписва всяка формула от теория на числада и донея 0 лии 1 ако е вярна иле не. Противоречи на теоремата на Гьодел за непълнотата, според която теория на числата е непълна теоря.
Ние - хората - нямаме констуктивно построение за въпросната редица <Ф1, 0>, ... и заради това и машината на Тюринг не може да го направи, т.е. не знаем как да построим такава машина. А как да можем? Според Гьодел не е възможно някой да сеети и да ни каже как се построява.
ОК?
| |
Тема
|
Re: Изчислимост -- оопппс
[re: ззз]
|
|
Автор |
Ray of Light (дала-багаин) |
Публикувано | 26.03.08 20:54 |
|
Не е възможно някой да се сети по чисто рационален път, но в възможно някой да го усети интуитивно
100 символа не стигат!
| |
|
Ако питаш дали може да се намери последното число след запетаята, не може, защото Пи е граница на безкрайна редица. Ако питаш дали може да се намери закон, по който да се предсказват цифрите след запетаята, мисля, че не може, но не мога да докажа това си твърдение а прима виста
100 символа не стигат!
| |
Тема
|
Re: Изчислимост -- оопппс
[re: Ray of Light]
|
|
Автор | 3зз (Нерегистриран) |
Публикувано | 26.03.08 21:35 |
|
Хе хе. Някой може да има интуиция, ама дали ще го докаже формално? Освен това в подобни непълни теории има безкраен брой твърдения вярни но недуказуеми твърдения (повечето без-интересни)... така че ще ти трябва безкрайно количество интуиция, за да се досетиш кои са вярните.
| |
Тема
|
Re: Изчислимост -- оопппс
[re: 3зз]
|
|
Автор |
Numberous (минаващ) |
Публикувано | 27.03.08 09:29 |
|
Ще ти кажа съображенията поради които питах тоя въпрос. В една доста сериозна книга от един доста сериозен учен прочетох, че съществуват изчислими и неизчислими реални числа. Пишеше, че "пи", "е" и корен квадратен от 2 са примери за изчислими реални числа. Но също пишеше, че повечето реални числа са неизчислими. Именно това ме интересува - кои именно са неизчислими? Изглежда, че не за всички реални числа могат да се измислят формули, генериращи последователно цифрите им (в десетичен запис). Аз питам дали някой наистина е чувал нещо по въпроса. Предположения мога разбира се и сам да си правя. Естествено благодарен съм за всеки отговор
Ne vsi4ko e vuzmojno, za6toto nqkoi ne6ta sa napulno sigurni
| |
|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | (покажи всички)
|
|
|