Rachunek kombinatorów
Z Wikipedii
 |
Niektóre informacje zawarte w artykule wymagają weryfikacji. Zajrzyj na stronę dyskusji, by dowiedzieć się, jakie informacje budzą wątpliwości. |
Rachunek kombinatorów (ang. Combinatory Calculi) to jeden z najprostszych możliwych uniwersalnych systemów formalnych.
Na język rachunku kombinatorów składają się kombinator stały K, kombinator rodzielonej aplikacji S, oraz kombinatory aplikacji złożone z pary dowolnych kombinatorów - funkcji i argumentu:
- σ = S | K | (σ σ)
Derywacją rządzą dwie reguły:
- ((K α) β) → α
- (((S α) β) γ) → ((α γ) (β γ))
Gdzie α, β i γ to dowolne kombinatory.
Tak prosty system jest w stanie wyrazić wszystko, co jest w stanie wyrazić rachunek lambda, dowolna maszyna Turinga czy w ogóle dowolny algorytm.
Kombinatory majÄ… prostÄ… interpretacjÄ™ w rachunku lambda:
- K = λ x . λ y . x
- S = λ x . λ y . λ z . (x z) (y z)
Często wprowadza się też kombinator identyczności I z regułą:
- (I α) → α
Ponieważ system SK już jest kompletny, kombinator ten można przepisać jako (SK)K:
- (((S K) K) α) → ((K α) (K α)) → α
Podobnie jak w rachunku lambda zwykle pomija się nadmiarowe nawiasy, zakładając wiązanie w lewo: α β γ to więc ((α β) γ).
Ponieważ każdy kombinator ma bardzo prostą interpretację w rachunku lambda, badania rachunku kombinatorów są zwykle częścią badań nad rachunkiem lambda.
Z zupełności systemu SK wynika, że każde λ wyrażenie bez zmiennych wolnych (w terminologii rachunku lambda również zwane kombinatorem) można zapisać za pomocą S i K, jednak ze względu na uboższy język, takie wyrażenia mają tendencję do przybierania bardzo dużych rozmiarów.
[edytuj] Przykłady
- Prawda - K
- Fałsz - KI = K(SKK)
- 0 - KI
- 1 - I = SKK
- Następnik - S(S(KS)K)
- Operator paradoksalny - S(S(S(KS)K)(K(SII)))(S(S(KS)K)(K(SII))) = S(S(S(KS)K)(K(S(SKK)(SKK))))(S(S(KS)K)(K(S(SKK)(SKK))))
Jak widać po przykładzie operatora paradoksalnego, rachunek kombinatorów może być i jest prostszy, jest jednak o wiele mniej czytelny od rachunku lambda.
[edytuj] Zobacz też
| Dlaczego warto uczyć kosmologii |
|
Kosmologia to młoda nauka fizyczna, której najgwałtowniejszy rozwój miał miejsce w XX wieku. Teraz w dobie wspaniałego rozwoju technik obserwacyjnych, ta nauka oferuje nam obraz pełnego piękna i tajemnic Wszechświata, w którym żyjemy.
|
| Jedna trzecia Polaków ma nadwagę |
|
Ponad połowa Polaków (51 proc.) może pochwalić się prawidłową wagą ciała; prawie jedna trzecia (32 proc.) ma nadwagę, a 14 proc. jest otyłych. 3 proc. to osoby z wagą poniżej wagi prawidłowej - wynika z sondażu TNS OBOP.
|
| Nad Biebrzą odkryto gród sprzed 7 wieków |
|
XIV-wieczny gród został odkryty przez suwalskich archeologów podczas prac na trasie budowy obwodnicy Sztabina (podlaskie). Archeolodzy znaleźli tam ok. 30 tys. zabytków. Odkryli przedmioty związane z życiem ludzi w grodzie, nazwanym - podobnie jak pobliska wieś - Horodnianka.
|
| Mikroskopijna hodowla komórek |
|
Mieszając wodną zawiesinę żywych komórek z odpowiednio modyfikowanym olejem fluorowęglowym można wytworzyć mikro kropelki, w których prowadzona jest długotrwała hodowla komórek. W ten sposób możliwe są bardzo zaawansowane badania biomedyczne, z wykorzystaniem różnych hodowli komórkowych, w jednym małym reaktorze hodowlanym, co znacznie obniża koszty badań, donosi "Lab on a Chip".
|
| Co pierwsze: jajko czy kura? Oto odpowiedź! |
|
Po raz kolejny okazało się, że bez pomocy Natury nowoczesna nauka nie ma szans. Używając białka z kurzego jajka jako matrycy, naukowcy zsyntetyzowali nieorganiczne, silnie magnetyczne nanorurki, donosi "Chemical Communications".
|