Příspěvky

7666

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 20:49:40 »

Šlo mi jen o to, že pokud mám dva programy pro své PC (což je FSM, jak říkáš), tak jejich ekvivalence je implementovatelná, je ale implementovatelná na tom PC?

Pokud se bavíme o skutečně praktické implementovatelnosti, tak odpověď je taková, jako v praxi téměř vždycky: Jak kdy
Např. když budu mít program, který má dva stavy (využívá jeden bit paměti)? V pohodě. Když budu mít program, který využívá 1GB? Hrubou silou těžko. Jde na analýzu takového programu použít nějaká heuristika? Určitě. Pomůže nám to problém vyřešit? To se uvií, až to zkusíme... No prostě normální "inženýrská" situace... To jenom v matice je všechno hnedka jasný jako facka...

Ale to je jedno, ať by to bylo tak nebo tak, základní otázku "K čemu vlastně potřebujeme TM?" to nijak neřeší. (na ni se Zz ptal) Odpověď na otázku "Je řešitelný problém zastavení TM?" nás nemusí pálit o nic víc než problém "Dá se povelem 'hot!' zastavit spřežení jednorožců?"

Jsou to prostě teoretické otázky na teoretické vlastnosti teoretického HW. Takže argumentovat, že je každý absolvent nutně potřebuje znát, je trochu... (každý ať si doplní sám)

A navíc si všimni, že ta teorie alespoň některé lidi zjevně spíš zblbne - myslí si, že vlastnosti TM můžou mechanicky aplikovat na reálný HW. Protože jim kdosi podal jakousi teorii, řekl k tomu jenom "TM je model počítače" - a skutečně se nad tím zamyslet a propojit to s praxí, na to už nezbyl čas - protože ty důkazy teoretických vlastností teoretických strojů jsou táááák složité...

No nic, mám nějakou práci, tak pro dnešek Jednorožcům třikrát nazdar!

7667

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 19:36:25 »

Jenom pro připomenutí - původně jsi reagoval na tohle:

Riziko že se budu marně pokoušet implementovat neimplementovatelný algoritmus si uvědomuji, jenže jediný takový problém který místní osazenstvo předvedlo je problém HP, ten se v praxi neřeší a teoretici to ani prakticky řešit neumí a žádný další předveden nebyl.

- u problému ekvivalence dvou programů pro FSM žádné "implementování neimplementovatelného algoritmu" nehrozí, protože ten algoritmus je implementovatelný.

7668

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 19:33:21 »

Umíme, ale umíme to nějakým pevným FSM?

Jde o to, co myslíš pevným FSM. Jakože bysme řekli, že FSM se sto stavy to dokáže pro libovolný FSM? To jistě ne. Ale to taky nikdo nepožaduje. Důležité je, že to je teoreticky řešitelné, čili informace, že pro TM to není řešitelné ani teoreticky je vcelku bezcenná, protože nám sděluje vlastnosti něčeho, co nemáme a nikdy mít nebudeme.

Co by nás mohlo zajímat, je počet stavů, které k tomu budeme potřebovat. To jo, to je zajímavá informace.

7669

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 19:17:49 »

Jo pardon, v první citaci se mluví o HP, ve druhé o ekvivalenci programů. Tak teď nevím, o čem je vlastně řeč.

Dokázat ekvivalenci dvou FSM ve standardním tvaru snad umíme, ne? To je druhá přednáška z formálů. O jakém problému je teda řeč?

7670

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 19:08:27 »

Ale stejně nemůžeš sestrojit FSM, kterému jen předhodíš program a vstup a ono ti řekne zastaví-nezastaví.

Dokaž!   (opakuju, že se jedná o program pro FSM - jak si ten FSM nadefinuješ, to je jedno - třeba jako TM s fixní délkou pásky)

Pokud nekonečnou páskou nahradíš nekonečnou hierarchií FSM, tak ano, pro nekonečnou hierarchií FSM je ta ekvivalence řešitelná.

Ne. Já mám za to, že program pro FSM je možné rozhodnout na FSM. Možná že se mýlím, ale to bych teda rád viděl ten důkaz.

7671

Hardware / Re:Velkorysé řešení automatizace

« kdy: 23. 10. 2012, 19:05:39 »

Z modbusu pouzivej jen fce
-Write Single Register (to spis kvuli nekterym softum)
-Write Multiple Registers
-Read Holding Registers
-Read Input Registers

Nojo, když já právě nechci jenom číst a nastavovat registry, potřebuju trochu jiné věci...

7672

Hardware / Re:Velkorysé řešení automatizace

« kdy: 23. 10. 2012, 18:54:58 »

Mě se osvědčil protokol RS232 na hardware CAN. Vzdálenosti stovky metrů, HW parametry o něco lepší než 485, je tam HW ochrana proti obsazení sběrnice a USART má dneska prakticky každý MCU.

Jenže 485 má lepší odolnost proti rušení, ne?

7673

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 18:46:36 »

A nebyla by tam ani jedna malá družice rozflákaná o povrch Venuše, když v ní program narazil na neřešitelný stav díky předchozí absenci analýzy z hlediska TM ? Já bych pak mohl říkat že programátor bez TM nemůže žít a tvářit se u toho tajemně

Jo, tak nějak to je

A proto je tak strašlivě důležité, aby každý absolvent TM nejen znal, ale uměl i dokazovat jeho vlastnosti Nehledě na to, že ani zdejší nějvětší zástánci tohodle, si to zjevně pořádně nepamatují

7674

Hardware / Re:Velkorysé řešení automatizace

« kdy: 23. 10. 2012, 18:38:02 »

Já teda nevím, ale I2C má omezení na 7,6m, 1wire 300m. To je dost rozdíl.

Máš úplnou pravdu, teď se mi to popletlo. Takže správně: u 1wire je nevýhoda v proprietárnosti, u i2c v krátkých vzdálenostech (prodloužení jde, ale je drahé).

Ethernet má každé PC, 232jku taky. Převodník na 485tku se dá vyrobit za stovku.
Jestli mám bastlit USB či 1Wire, tak si raději napíši Modbus slave.
Trvalo mi to na AVRku 2 večery v céčku.
Pod windows si stáhnu třeba Promotic http://www.promotic.eu/cz/index.htm (25 proměnných je zdarma) a jedu.

Doporučuješ teda 485? Tu jsem si vybral taky.

A jako protokol Modbus? Jaké bys případně doporučil alternativy? Na Modbusu se mi moc nelíbí ta (zdá se mi na první pohled) jednoúčelovost - 1B function code mi přijde docela málo, používají se v praxi ještě nějaké další protokoly nad tím?

7675

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 18:05:38 »

U niektorých programov sa predpokladá dlhá doba výpočtu a tam je zistenie zložitejšie / nemožné a o takých programov nám ide.

Jako možná někde je, ale praktiky si to neumím moc dobře představit. Dlouhý výpočet se logicky vždycky skládá z nějakých iterací a měl by konvergovat nějakým směrem. Kontrolovat průběžně konvergenci bude v praxi nejspíš v 99.9% stačit...

A co ta ekvivalence programů?

A já si myslel, že jsme si složitě vysvětlili, že reálné počítače jsou FSM...

A pro některé programy je HP také trivka

Myslíš "pro všechny normální programy, se kterými se normální smrtelnk potká?"

Přitom Büchiho automat si v praxi jako HW nesestavíte

Mám takový matný pocit, že Zz-a by spíš zajímalo, co si díky znalosti TM může sestrojit - což není nic, protože TM se hodí na důkaz toho, že něco nejde, ne naopak.

Možno nie až tak - akurát viem povedať, že to ušetrilo kopu peňazí na pokusy o implementáciu riešenia HP štýlom "skončí to do 25 dní, ale keď príde signál X, tak to skončí do 29 dní, inak to skončí do ...". Namiesto toho to aj po odstránení bugu môže riešiť pracovník pomerne úspešnou heurestikou ako "už druhý deň pravidelne bliká LED na zariadení a zdá sa, že sa to pomerne hreje, tak sa to asi zacyklilo".

No tak to je právě nesmysl. Víme, že pro FSM (kterému reálný HW odpovídá) je HP řešitelný, čili poznatek, že pro TM je neřešitelný, nám neušetřil ani halíř - protože prostě v praxi zjišťujeme, že něco, co by teoreticky mělo jít, nejde kvůli fyzickým omezením.

Takto teoreticky s tím nemám absolutně žádný problém. Jen bych to chtěl vidět na vlastní oči. I důsledky obecné teorie relativity se dají pozorovat v praxi, tak určitě půjde i tohle.

No dostal jsi tři případy něčeho, co nejde, a víme to díky TM. Nic víc čekat nemůžeš, TM  je přesně na tohle - dokázat, že něco nejde ani na idealizovaném nekonečném počítači.

7676

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 11:19:29 »

To nepochybuji, jenže kolik takových úloh v praxi potkáš.

Žádnou. V praxi se obvykle snažíš řešit to, co je intuitivně jasně řešitelné.

Čili dokud nebudu mít jasno takovým způsobem, že například bez TS nebudu umět program na podvojné účetnictví, tak je to slabota.

No tak on TS je formální nástroj pro dokazování, nic jiného. Takže se musíš ptát, jestli je nějaká běžná úloha, pro jejíž naprogramování nutně potřebuješ vědět nějaký důkaz. To asi není. Respektive jestli je, tak je to nějaká obskurnost v nějakém obskurním jazyce (a takové úlohy mají řešit teoretici, proti tomu snad nikdo nic nenamítá).

V běžném životě na nic takového nenarazíš... Daleko pravděpodobnější by bylo, že bys v praxi narazil na úlohu, která pomocí TS řešitelná je, ale prakticky není - ale to poznáš velmi rychle, protože v tom algoritmu prostě budeš podezřele často (a bezmezně) alokovat paměť.

Pro praktické věci se daleko víc hodí ty FSM nebo LBA, tam si dovedu praktické použití představit docela lehko. Nebo se třeba hodí vědět, že PDA se dvěma zásobníky má stejnou výpočetní sílu jako TM, to se taky může hodit, když třeba chceš zkonstruovat nějaký jednoduchý VM nebo tak něco...

7677

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 10:22:42 »

Celým smyslem debaty bylo uvědomit si, že TS v praxi nepoužijete

V tomhle se musím matematiků trochu zastat. Pokud dokážeš, že nějaká úloha nejde řešit Turingovým strojem, víš naprosto jistě, že nepůjde řešit ani skutečným strojem. Nebo ještě jinak: víš, že řešení té úlohy není závislé na paměti - i kdybys jí měl nekonečně mnoho, stejně to nevyřešíš. Potud to aspoň v bujné představivosti nějaký smysl má.

Blbý je to s opačným problémem - dokázat, že něco na normálním počítači řešit půjde. To už pomocí TS prostě dokázat nejde, protože TS má (reálně, prakticky) větší výpočetní sílu než jakýkoli počítač, který kdy bude sestrojen.

Co se týče praktičnosti, tak jsou na tom o něco líp LBA, tam už je podobnost se skutečným HW docela slušná. Paměť je sice pořád potenciálně nekonečná, ale aspoň je svázaná s délkou vstupu, takže můžeme říct něco ve stylu "ke zpracování obrázku velkého 1MB potřebujeme 1GB paměti", což je už docela prakticky použitelné.

7678

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 09:56:18 »

A mimochodem, nejjednodušší automat, pro který je obecný problém zastavení nerozhodnutelný, je "counter automaton" (nevím, jak se tomu říká česky, asi automat s čítačem). Stačí jediná paměťová buňka, schopná držet neomezené přirozené číslo.

Proč?

No protože držet "neomezené přirozené číslo" vyžaduje mít k dispozici neomezené množství paměti - a z toho právě plyne neomezené množství stavů a tímpádem ta nerozhodnutelnost.

Čili "teoretická nerozhodnutelnost" je čistý jednorožec. V praxi hraje a vždycky bude hrát roli jenom "praktická nerozhodnutelnost".

7679

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 23. 10. 2012, 09:17:21 »

Kdyz budu u tveho prikladu, pak podle tebe, konecny automat, ktery rozeznava jazyk a^n pro vsechna n take nelze prakticky postavit, protoze na to rozeznani spotrebuje nekonecne casu. Ale to neni pravda, protoze je rozdil mezi "spotrebuje nekonecne casu" a "spotrebuje libovolne velke mnozstvi casu".

No to samozřejmě NENÍ pravda - a je to úplně jiný případ:

Jazyk a^n je regulární a na jeho rozpoznání mi stačí FSM se dvěma stavy: první stav se jmenuje "doposud byly na vstupu jenom áčka" a druhý se jmenuje "už jsem dostal i něco jiného" - ten první je akceptující a přes áčko se jde zpátky do něj, přes cokoli jiného do druhého stavu. Potřebuju teda jenom jeden bit paměti, nic víc.

Pochopitelně je nesmysl "potřebuji nekonečný čas". Že automat rozeznává jazyk a^{n} znamená, že mu můžu předhodit libovolně dlouhý (konečný) řetězec "aaaa..." a on mi správně odpoví - opakuji: libovolně dlouhý.

Automat akceptující jazyk a^{n}b^{n} je úplně jiný případ - k tomu, aby uměl správně akceptovat libovolně dlouhé slovo, musí mít automat k dispozici buď nekonečnou paměť, nebo musí mít instrukci "alokuj další pamět", kterou může použít kolikrát chce a ta instrukce nikdy neselže - protože automat prostě musí někam ukládat, kolik áček zatím dostal - a ta hodnota je neomezené přirozené číslo, tudíž potřebuji mít k dispozici neomezené množství paměti. To pochopitelně neznamená, že musím mít k dispozici "aktuálně nekonečnou" paměť, ale musí být alespoň "potenciálně nekonečná", protože dopředu nikdy nevím, kolik jí skutečně budu potřebovat.

Takový jazyk není regulární a pro jeho rozpoznání potřebuju minimálně PDA, které má ex definitio k dispozici neomezené množství paměti.

Takový stroj ale nemáme a nikdy mít nebudeme. Vždycky budeme mít jenom OMEZENÉ množství paměti, což znamená, že každý fyzický stroj, který máme a kdy budeme mít, bude schopen rozeznat jazyk a^{n}b^{n} jenom pro n menší než nějaké k, což je množství dostupné paměti. Slovo a^{k}b^{k} už stroj nebude schopný rozpoznat, protože tak velké k už se mu prostě nevejde do paměti. Proto neexistuje a nikdy nebude existovat fyzický stroj, který by uměl rozeznávat celý jazyk a^{n}b^{n} - tj. a^{n}b^{n} pro libovolné přirozené n.

7680

Hardware / Re:Velkorysé řešení automatizace

« kdy: 23. 10. 2012, 09:02:56 »

Skus 1-wire, třeba tě to nakopne http://quattro.haje.cz/index.php/elektronika/domaci-automatizacez

1-wire je dobrý pro komunikaci se součástkami na krátké vzdálenosti. Na delší vzdálenosti to sice jde taky, ale pokud si dobře pamatuju, "retransmitter" (sorry, nepamatuju si, jak tomu přesně říkají) byla poměrně dost drahá součástka.

Taky co jsem tak v diskusích narazil, problém je, že 1-w je proprietární protokol a výrobci nevadí, když si člověk naprogramuje master, ale slave-y by raději prodávali oni... viz

NOTE: It appears that Dallas Semiconductor doesn't like people who
implement 1wire slaves in software.

On the other hand, they do discontinue ICs like the DS2423 counter
for which no substitute exists.

Therefore, while I cannot prevent people from doing whatever they want,
simulations of existing ICs will only be entered into this project's
repository if the ICs are no longer available or (at the very least)
"not recommended for new design". Sorry if you want more, but IMHO
this is the best compromise between practical and legal considerations.

https://github.com/smurfix/owslave

To mě trochu odstrašilo od použití 1-w jako hlavní komunikační sběrnice... Navíc i2c je srovnatelná a součástky myslím dostupnější, takže bych raději volil tohle.