Co znamená i-té slovo

Uživatelský avatar
Cabroušek
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 24. 1. 2008 23:16
Typ studia: Informatika Mgr.
Bydliště: Kladno
Kontaktovat uživatele:

Co znamená i-té slovo

Příspěvek od Cabroušek »

U diagonalizačního jazyka L_ {DIAG} = \{ w_i \in \{0,1\}* | w_i 
ot\in L(M_i) \} nebo například v důkazu věty 2.1.2 v Kučerových poznámkách (na str. 29) se používá označení w_i.

Mohl by mi, prosím, někdo vysvětlit, co se tím myslí? Nemůžu na to přijít a přijde mi, že je celkem zásadní to vědět.
Uživatelský avatar
MacJariel
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 23. 1. 2007 15:07

Re: Co znamená i-té slovo

Příspěvek od MacJariel »

Je to jeho způsob jednoznačného převodu mezi binárními řetězci a přirozenými čísly. Viz strana 8 v jeho poznámkách:
Mějme binární řetězec w a přiřaďme mu přirozené číslo jehož binární zápis je 1w. Prázdnému
řetězci ε tak odpovídá 1, řetězci 0 odpovídá číslo 2, řetězci 01 odpovídá číslo 5 a tak podobně.
Toto přiřazení je zřejmě vzájemně jednoznačné, tj. kladnému číslu jednoznačně odpovídá ře-
tězec a naopak, dostali jsme tedy očíslování binárních řetězců, i-tý řetězec budeme označovat
pomocí wi.
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“