# XBUP - Základní teze projektu

### Úvod

Tento dokument je součástí dokumentace projektu eXtensible Binary Universal Protocol. Obsahuje popis základních tezí formalizace protokolu.

O úroveň výše

### Obsah

1. Základní teze
1.1. Reprezentace dat
1.2. Teorie univerzálního protokolu
1.3. Konečná množina
1.4. Spočetná množina
2. Reference

### 1. Základní teze

XBUP jakožto univerzální protokol by měl na prvním místě umožňovat realizovat libovolná data co nejjednoznačnějším způsobem. Následující dokument popisuje snahu o formalizaci tohoto tvrzení.

### 1.1. Reprezentace dat

Cílem protokolu je reprezentace dat ve formě bitové posloupnosti, přičemž tato posloupnost může být potenciálně nekonečně dlouhá. Bit je základní jednotka informace a pro potřeby formalizace budeme bity reprezentovat jako prázdnou množinu pro bit 0 a množinu obsahující pouze prázdnou množinu jako bit 1, tedy oborem hodnot je tedy množina B = { ∅, {∅} }, známá také přímo pod označením 2.

Oborem reprezentace dat je pak posloupnost bitů N x B. Na této množině je pak definováno uspořádání po složkách. Pro množinu N přirozených čísel je použito klasické uspořádání < a pro bity platí, že ∅ < {∅}

Toto uspořádání je dobré uspořádání dle definice:

- ireflexivita - neplatí pro žádné x: x < x
- antisymetrie - pro každé x a y platí: x < y ∧ y < x ⇒ x = y
- tranzitivita - pro každé x, y a z platí: x < y ∧ y < z ⇒ x < z
- každá neprázdná podmnožina má nejmenší prvek - pro každou množinu P: P ⊆ S existuje x takové, že pro každé y ∈ P platí: x = y ∨ x < y

Instancí reprezentace dat je pak funkce f: N → B ∈ N x B. Každá instance dokáže uchovat pouze spočetné množství dat. Instanci nazýváme konečnou, právě když platí: ∃ x: ∀ y: y > x ⇒ f(y) = 0.

### 1.2. Teorie univerzálního protokolu

Autor tohoto protokolu se domnívá, že stejně jako v případě Churchovy teze, je lze i pro výše definovaný předpis definovat hierarchii a že je možné definovat právě jeden tvar protokolu, který je v jistém smyslu minimální.

Existuje univerzální protokol, který dokáže reprezentovat každý objekt univerza se spočetnou složitostí v základním tvaru, pro který platí:

- Pokud je možné objekt rozložit na více objektů, není objekt v základním tvaru.
- Reprezentace musí být schopna uložit spočetné množství konečných instancí sama sebe a alespoň jednu nekonečnou instanci

### 1.3. Konečná množina

Pro reprezentaci prvků konečných množin je možné využít faktu, že dobře uspořádané množiny se stejnou mohutností jsou vzájemně izomorfní. Pro reprezentaci těchto množin je možné použít binární reprezentaci indexu prvku na n-tici bitů délky alespoň

### 1.4. Spočetná množina

Pro reprezentaci prvků spočetných množin není možné použít předchozí postup, respektive ten je možné použít právě jednou.

### 4. Reference

http://en.wikipedia.org/wiki/Bit

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2008-06-30