пи=корен квадратен 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

В повечето формули които си дал няма неква особена хитрост.
Първата се доказва по много начини, има включително изцяло геометрично доказателство (правили сме го в училище едно време).
Втората се извежда с ред на Тейлър на ф-ята arctan(x).
Третата (формула на Уолис) се извежда например тук:

Съдържаниет е скрито
Влезте за да го видите

Тази система "Lambda Calculus" е била замислена от Чърч да се ползва за пресмятане и доказване на твърдения. Първоначалната му система се оказва противоречива (доказано от 2-ма негови аспиранти Клини и Росер), но после Чърч я оправя. Както и да е, доказано е че системата на Чърч е еквивалентна на други концепции, като машината на Тюринг (доказал го е самия Тюринг), на продукционната система на Пост, на рекурсивните функции на Гьодел, на системата на Марков. Тази еквивалентност е накарала по-късно Чърч да постулира своята "Хипотеза на Чърч".

Това е от раздел "теория на рекурсията", под-раздел на математическата логика.

Има доста пълна и изчерпателна книга по Ламбда Смятане:

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

А знаеш ли, дали за всяка числова редица може да се състави формула, генерираща последователно елементите и?

Ne vsi4ko e vuzmojno, za6toto nqkoi ne6ta sa napulno sigurni

Разбира се че може. Може да се състави ламбда-израз, да се построи машина на Тюринг, или да се напише компютърна програма, която изброява елементите на редицата.

Нали според така наречения "Тезис на Чърч" който ти спомена на друго място, това което изобщо може да сметне човек (да изброи, калкулира, да изпише..) може да го направи машимата на Тюринг, ламбда-смятането, и т.н. Даже повече -- човек е смъртен и бавно смята. Една машина на Тюринг (или компютър) може да работо 1000 години и да изписва поредния знак от числото ПИ. Самия ред е безкраен и никога няма да спре да се изписва .. но важното е че машината може да достигне до които и да е знак... ако трябва да работи и 2000 години :)

(което не значи, чв няма неразрешими проблеми; в теория на рекурсията се доказват много теореми за не-разрешими проблеми - нито машината на Тщринг нито човек е в състояние да ги реши; например логиката от 1-ви порядък е неразрешима, както показва и теоремата на Гьодел - т.е. има достатъчно силни теории в които има верни твърдения но не-доказуеми).

Оопс.. не обърнах внимание на думите <за всяка редица>; имах в предвид всяака числова редица която можем да дафинираме <конструктивно> - за нея може да се построи ламбда израз.

В общия случай не може.

Пример:

-- Може да се напише програма (или ламбда израз) който да изброява и исписва всички твърдения в теория на числата ф1, ф2, ф3, ... Това е сигурно че може.

-- Обаче не може да напишам програма която изпива например такъв ред: <ф1,0>, <Ф2,1>, <ф3, 1>, <ф4,0>,.... т.е. да изписва всяка формула от теория на числада и донея 0 лии 1 ако е вярна иле не. Противоречи на теоремата на Гьодел за непълнотата, според която теория на числата е непълна теоря.

Ние - хората - нямаме констуктивно построение за въпросната редица <Ф1, 0>, ... и заради това и машината на Тюринг не може да го направи, т.е. не знаем как да построим такава машина. А как да можем? Според Гьодел не е възможно някой да сеети и да ни каже как се построява.

ОК?

Не е възможно някой да се сети по чисто рационален път, но в възможно някой да го усети интуитивно

Съдържаниет е скрито
Влезте за да го видите

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

Съдържаниет е скрито
Влезте за да го видите

Хе хе. Някой може да има интуиция, ама дали ще го докаже формално? Освен това в подобни непълни теории има безкраен брой твърдения вярни но недуказуеми твърдения (повечето без-интересни)... така че ще ти трябва безкрайно количество интуиция, за да се досетиш кои са вярните.

Съдържаниет е скрито
Влезте за да го видите

Ще ти кажа съображенията поради които питах тоя въпрос. В една доста сериозна книга от един доста сериозен учен прочетох, че съществуват изчислими и неизчислими реални числа. Пишеше, че "пи", "е" и корен квадратен от 2 са примери за изчислими реални числа. Но също пишеше, че повечето реални числа са неизчислими. Именно това ме интересува - кои именно са неизчислими? Изглежда, че не за всички реални числа могат да се измислят формули, генериращи последователно цифрите им (в десетичен запис). Аз питам дали някой наистина е чувал нещо по въпроса. Предположения мога разбира се и сам да си правя. Естествено благодарен съм за всеки отговор

Ne vsi4ko e vuzmojno, za6toto nqkoi ne6ta sa napulno sigurni