Zde byl jen hezky prakticky a pro laiky demonstrovan halting problem a jeho "dukaz" bez nutnosti znat prislusne formalismy. Tedy nechapu, co myslis tou "famou".
S tim rici, zda hodinu neodpovidajici program je zacykleny, to nemusi byt zcela jednoduche ani v praxi, zalezi na komplexite prislusneho software - kdyz ti nebude hodinu odpovidat notepad, tak asi neco spatne bude, kdyz hodinu nebude mit zadny vystup program pro nejake numericke modelovani, tak vse muze byt v nejlepsim poradku. Ta tva hodina je jen empiricky zjistena doba, kdy by mel konkretni program na obvyklych datech neco provest.
Pokud to bylo na muj prispevek, tak jste si zrejme nevsiml smajliku ( ;-) ), kterym je cela veta postavena do humorneho tonu (tedy vtipek pro uchechtnuti, nic vic - nebylo to mireno ani na autora ani na korektorku, pouze jsem se chopil prilezitosti a chytlaveho slovniho obratu :-) ).
Mne to teda vyčíslitelnost nepřipomíná. Když už tak složitost (redukce všech problémů na problém zastavení, který nelze řešit a proto mají všechny uvedené úlohy stejnou složitost NP), ale spíš docela obyčejné formální jazyka a gramatiky typu 0 v Chomského hierarchii... Vyčíslitelnost mi přijde jako podstatně větší věda.
Halting problem je problem vycislitelnosti - staci si zajit na zakladni prednasku z ni. Ve slozitosti se jiste tak dukladne nerozebira, protoze z hlediska slozitosti neni az tak zajimavy (naproti tomu ve vycislitelnosti se pak vede mimo jine i teorie kolem relativizovaneho halting problemu atd.). Kdyz zminujes jazyky typu 0 a vubec Chomskeho hierarchii, tak ty problemy jsou ovsem provazane - v teorii gramatik se halting problem vynori opet v podobe problemu rekurzivnich a rekurzivne spocetnych jazyku.
Slozitost se zabyva totalne vycislitelnymi funkcemi, coz problem zastaveni neni (neni totalni). I NP problemy jsou totalne vycislitelne, a proto z hlediska vycislitelnosti nezajimave.
Popularizacni clanky o teoreticke informatice jsou jiste zajimavym ozivenim, skoda jen, ze ROOTa ctou z velke casti lide, kteri se s problematikou potkali ve skole mnohem podrobneji.
Letos jsem promoval z informatiky na Mendelu, takže můžu potvrditm že tento problém jsme vyřešili a za utržené peníze se staví nová budova (5 pater podzemních garáží a protiatomový kryt, 8 pater nad zemí - horní polovina "Top secret" výzkumná část). CIA prostě platí "very well"...
A dávejte si bacha, velký bratr se dívá
> (redukce všech problémů na problém zastavení
> ,který nelze řešit a proto mají všechny uvedené
> úlohy stejnou složitost NP)
Velmi vtipne :)
Mate na mysli skutecne NP? Nemel jste temi "problemy ktere nejdou resit" na mysli tridu problemu NP-uplnych? (ale i tak je to scestne).
NP je podle Vas trida problemu ktere nejdou resit? Spise se jedna o tridu problemu ktere se daji resit nedeterminsiticky v polynomialnim case, ne? Jak s touto tridou problemu souvisi halting problem, ktery nejen ze se neda resit ani nedeterministicky v polynomialnim case, on je proste nerozhodnutelny.
No, maly ulet se obcas stane kazdemu, ale mel jsem za to, ze jste "head of Institute for Informations and Informatics Mendel University", coz pokud je pravda, tak jste se, s dovolenim, ponekud ztrapnil.
Dobrý den,
chtěl jsem se zeptat, zda je z definice TS páska opravdu nekonečná z obou stran od hlavy TS. Já jsem se kupříkladu setkal s popisem TS takového, že páska je sice nekonečná, ale má počátek (v podstatě polopřímka). Při startu programu je hlava na prvním symbolu na pásce a zastavení se neprovádí instrukcí STOP ale tím, že hlava z pásky "vypadne", tj. na prvním symbolu dostane příkaz L.
Asi takto
> . . . . . . . . . .
^
L
PS: vypadá to, že obě pojetí TS jsou ekvivalentní (už jen tím, že vícepáskový TS lze simulovat na jednopáskovém, takže dvě polonekonečné pásky by také šly simulovat)
Existuje mnoho modelu TS - stroj s vice hlavami, s vice paskami, s omezenym poctem stavu, omezenym poctem symbolu, omezenym mazanim, jednostranne nekonecnou paskou... Lze ukazat, ze zasobnikovy automat se dvema zasobniky je uz ekvivalentni TS, existuji jeste horsi vymysly, ktere pres svou blaznivost jsou ekvivalentni TS. Jakmile dokazete ekvivalenci sveho formalismu s TS, tak mate vyhrano, muzete si pouzit formalismus, ktery vam vice vyhovuje, vsechno pro TS vude platit i pro vas a naopak. Napr. ve vycislitenosti se pracuje misto s TS typicky s castecne rekurzivnimi funkcemi, coz je mnohem abstraktnejsi formalismus nez TS, ale je ekvivalentni a pro mnohe veci elegantnejsi.
Ano, to vim. Celkem zajimavou zabavou jsou ruzne postupy a dukazy na "redukci" ruznych stroju (napr. vicepaskove) na jednopaskovy TS. Me jen zajimalo, ktera z techto verzi TS je svym zpusobem minimalisticka, tj. obsahuje co nejmensi mnozstvi pasek/hlav/vnitrnich stavu/symbolu, ale pritom ji zustavaji vyjadrovaci schopnosti plneho TS.
Co jsem zatim videl, tak "nejmensi" je TS s jednostranne nekonecnou paskou, jednou hlavou, ktera umi pouze operace L a R a na pasce mohou byt pouze binarni symboly 0 a 1. Samozrejme ze prvni veci, ktere tento TS musi umet je simulace TS s rozsirenou sadou symbolu na pasce.
Obavam se, ze nelze rici, ktera verze je nejminimalistictejsi. Napr. lze udelat TS s pouze dvema aktivnimi stavy, ale zase na ukor nafouknuti abecedy, a naopak lze udelat TS pouze s jednim symbolem (kdyz nepocitam lambda = prazdny symbol), nicmene s mnoha stavy. Dokonce jak jsem zminoval TS s omezenym mazanim, tak to je TS, ktery ma povoleno pouze "kankovani" na pasku, kde kanky uz nesmi po sobe mazat nebo prepisovat na neco jineho nez kanky.
Pro me osobne asi nejdabelstejsi verze TS, o niz jsem slysel, byla "ctyri pocitadla", kde pocitadlo si lze predstavit jako jednostrane nekonecnou pasku, na ktere lze hlavou jezdit vpravo i vlevo, ale nelze na ni zapisovat. A mam pocit (ale tohle uz je ber s rezervou), ze dokonce je snad mozna konstrukce pouze se dvema takovymi pocitadly.
Díky moc za odpověď.
Ten TS s počitadly mi trošku připomíná BBPL - Bare Bone Programming Language. To je progamovací jazyk, který zná jenom konstrukce ++, -- a while !0 (inkrementaci, dekrementaci a smyčka s testem na nulo). Tam se například přiřazení musí udělat pomocí dvou smyček apod. Napsat v něm lze všechny algoritmy, ale pouze za předpokladu, že buňky buď mají neomezený rozsah hodnot, nebo je nekonečný počet buňek...
To nebyla chyba operatora, ale toho, kdo ten postup naridil (?Schifferburo?). A Turing mimo jine vymyslel konstrukci 'bombe', coz byl zjednodusene receno desifrovaci stroj na Enigmu.
(sloziteji receno to byl stroj schopny overit nektere hypotezy o nastaveni enigmy pouzitem pro zasifrovani predlozeneho kusu ciphertextu)
Vrele doporucuji knihu od Hugha Sebag-Montefiore, Enigma: The Battle for the Code, je tam (hodne) o tom, jak ji lustili Polaci, jak fungovaly ruzne metody na lusteni atd.
I o chybach operatoru :-)
Teplej je ledaskdo - jako treba ja :-) Neni divu, na svete je podle aktualnich odhadu 120 000 000 gayu. Napriklad ten co napsal sendmail je gay a mam pocit ze dokonce jeho pritel nejak delal do BSD nebo sysv4 - ted uz presne nevim. David Madore co maintainoval driv bsd-ftpd ma taky na svy strance masitou sekci s gay odkazama ;-)
Celkem by me zajimalo jestli jsou tady mezi ctenarema taky nejaky lidi predmetneho razeni (teoreticky by mel bejt kazdej 25-tej nepocitame-li holky). Zajimalo by me treba taky jaky dalsi volne siritelny projekty priletely z teplych krajin ;-)
nno :)
tak teda v tomto ohlade patrim k 96% vacsine, aj ked si obcas myslim ze by mozno bolo vyhodnejsie konvertovat k 4% mensine, pretoze tam kde sa ja povacsinu casu vyskutujem (tj. tam kde zvykne byvat problem = medzi klavesnicou a stolickou) sa zeny vyskytuju fakt zriedka :[]
V Gnome existoval program GTuring, který dělal to, co bych od simulace Turingova stroje očekával. Ve svoji distribuci ho teď nenajdu, takže si ho nenainstaluju, a u Gnome se mi ho nepodařilo stáhnout (tak to nevím proč). Takže pivo asi nebude. (snad by autor uznal odhad (počet kroků) > (něco velkého) za dostačující).
Asice, nektere 'slusne programatory', kteri pisou prehledne, zato jejich 'nadrizeni' maji vlastni styl programovani (dosti neprehledny), a pro ktere, kdyz volani jakekoli metody neni na jedine radce kompletne definovane, jsou zdrojaky spatne napsane.
Samozrejme se potom jedna rovnez o neprehledny kod, bohuzel napsany 'project manazerem', ve kterem se ani cert nevyzna. Inicializace objektu ci pointeru zadna, komentar vytvorenych metod zadny. Atd. Vysledkem je, ze novy clovicek, ktery se po letech diva na kod, se ho zbytecne 'musi' ucit zpameti, nez ho zacne vyuzivat/pouzivat.
Tohle je nejvetsi svinarna programatoru: nulova dokumentace metod a trid, nulova inicializace objektu. Jen proto, ze programator 'predpoklada, ze....' se mu ten objekt asi zinicializuje sam. Proste se drzi sloganu, ktery ja vzdy trosku pozmenim, asice 'Programator predpoklada ze ... access violation'.
Co je na tom nejhorsi, ze takovito svinaci nejsou jen mezi programatory, ale i vyse.
Já jsem slovo "pumlíč" slyšel v Hurvínkovi (Spejbl: "Za tím pumlíčem si lítej sám!"), v souvislosti se souslovím "kopací meruna" a "mičuda" :o).
Ale k věci. Použil jsem veřejný přístup do korpusu PUBLIC [ČNK] - obsahuje 20 miliónů slov - a výsledek je žalostný. Žádný výskyt (query "[Pp]umlíč.*"). Trochu mne to překvapilo, a tak bych chtěl požádat někoho, kdo má přístup k ostatním korpusům (korpusový manažer QCOP), aby tuto skutečnost prověřil.
[ČNK] Český národní korpus, http://ucnk.ff.cuni.cz/
Korpus mi prijde o neco horsi nez ta databaze pro scrabble. Korpus se vytvari z ruznych pramenu, napriklad novin, takze kdyz dame v korpusu hledat slova s chybami, tak je to taky najde.
Napr:
nabídnuty k escontu , by se neměly nechat ZVYKLAT ani nejrůznějšími průvodními dokumenty.
Ten slovnik pro scrabble by snad nemusel obsahovat hrube chyby.
Pumlic by se mohl brat taky jako slovo vznikle zamenou dvou pismen ve slove pulmic (jako polovina mice) :-)
<pre>
char *halting_problem (..)
{
struct sandbox A, B;
struct prog P;
int ff = 0;
read_prog (&P, stdin);
init_sandbox (&A, &P);
init_sandbox (&B, &P);
while (! is_halted (&A)) {
step_next (&A);
if (is_equal (&A, &B))
return "program se zacykli a neskonci";
if (ff ^= 1)
step_next (&B);
}
return "program se zastavi";
}
Jen dodam, kdyby to nekomu nahodou nebylo jasne na prvni pohled. Program je simulovan v sandboxu, coz je jakysi simulacni model pocitace, na kterem program pobezi. Nejprve nactu program, a poslu ho do DVOU sandboxu. Stacil by i jeden, ale detekce zacykleni by byla slozitejsi, musel bych uchovavat historii vsech stavu. Pak se program zacne soubezne provadet v obou sandboxech, v tom prvnim 2x rychleji. Ze smycky se vypadne bud kdyz program skonci ve stavu oznacenem jako konecny (is_halted vrati true), nebo zjistim ze okamzita konfigurace obou sandboxu je stejna (tj stejny algoritmus se po provedeni 2N kroku ocitne ve stavu kde byl po N krocich, je tedy zjevne ze ve stejnem stavu bude i po K*N krocich, a K muzeme poslat do nekonecna.
Muj program proto A) spravne reportuje kdyz program skonci B) spravne pozna kdyz se program zacykli. Vazne nevim co ti vedatori resi. :)
Je treba si uvedomit, ze simulovany program muze alokovat nekonecne mnozstvi pameti (nad konecnou pameti ma uloha zastaveni samozrejme reseni). Tzn program je schopny generovat stale nove a nove stavy az do nekonecna (lze si napr. prestavit, ze treba pocitam hodnotu pi). Tvuj program da odpoved v pripade, ze se program _necykli_, na tuto odpoved ale neni treba psat nejaky specialni kod, proste zkoumany program spustim.
P.S. Ad Milan Sorm, rad bych ctenare teto diskuse ubezpecil, ze _vyznamna_vetsina_ absoloventu FI MUNI chape rozdil mezi problemy ze tridy NP a problemem zastaveni.
K čemu je dobrý program, který alokuje nekonečně mnoho paměti? A hlavně kde ho chcete spouštět? Program který nelze spustit nemá smysl analyzovat, nemyslíte? Jde o teoretický konstrukt (čti výmysl) a přemýšlet nad ním je zhruba stejně zbytečné jako soutěž v čurání do dálky.
Tak specialne pro absolventy a studenty FIT VUT: Predstavte si program, ktery pricita jednicku k promenne x, kterazto nemuze pretect, protoze prostor tohoto cisla je alokovan dynamicky. (Pro ilustraci treba podobne jako v bc.) Toto je jenom vylepsena verze "alokatoru pameti", ktery ji ale alokuje jenom logaritmicky rychle (teda spis pomalu). Jinymi slovy uz na par megabajtech vypocet predstavje nekolik dob existence slunecni soustavy, tudiz sandbox je uplne na ... (Informatikovi normalne staci predstava "rychleho" alokatoru pameti na nekonecnem datovem, holt pro VUT je to vysvetlovani trochu pomalejsi.)
No a jadro psa je, ze by se docela hodilo, kdybych dokazal zjistit, zda se muj vypocet ubira stejnou cestou, jako "pomaly alokator pameti", tj. nikdy neskonci, nebo zda bude nekdy koncit. No a to se nikdy nedovime, protoze problem zastaveni. No a dobre je to k tomu, ze se uz nemusim snazit napsat obecny detektor zastaveni, protoze to nejde, nebo to muzu dat nejakemu VUTakovi abych se ho na par dni zbavil. :P
Znam spoustu kvalitnich absolventu a studentu VUTu, (a nekvalitnich studentu a absolventu FI, jejichz perly lze nalezt i v teto diskusi :) ale bez takove vulgarni generalizace by nikdy nemohl vzniknout poradny flame. A kde jinde si muze clovek zaflamovat, nez prave ve foru k podobnemu clanku?
$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2^2^2^2^2^2^2^2^2^2^2
Runtime error (func=(main), adr=38): exponent too large in raise
Hmm, asi pouzivate jiny BC, zejo? Matfyzaci si asi vydupali neco extra :-) :-)
> 2^2^2^2^2^2^2^2^2^2^2
> Runtime error (func=(main), adr=38): exponent too large in raise
Nevim co jste snazil timhle demonstrovat. BC vskutku alokuje pamet dynamicky, dokud ovsem zbyva co alokovat. Cislo 2^n pro n>ULONG_MAX se proste do pameti nevejde, a je jiste uzitecnejsi ohlasit rovnou "exponent too large", nez pocitat a pocitat a pocitat a nakonec zhynout na nedostatek VM.
Vašek tvrdil že předpokládat "nepřetečitelný" counter je zcela legitimní a rozumný předpoklad, a uvedl BC jako příklad. To jestli BC chcípne hned nebo až později je jedno, důležité je že chcípne, tedy nepřetečitelný counter neumí, stejně jako jej nikdy nebude umět žádný počítač. Proto je abstrakce konečného automatu zcela adekvátní pro libovolný myslitelný počítací stroj.
Tohle muze rici nejspis jen clovek, ktery si nevidi dal nez na spicku nosu. Nebo je to frustraci ze zjisteni, ze i ta nejnabusenejsi masina, kterou lze sehnat, je v principu jen konecny automat?
Kdyby uz nic jineho, tak teorie vycislitelnosti prinasi jeden velice prakticky dusledek halting problemu: nelze automaticky verifikovat software (snad kazdy rozumny clovek bude souhlasit s tim, ze rici, co dany program dela, je tezsi nez zjistit, zda vubec konci). Mimochodem halting problem souvisi s mnoha jinymi problemy, nekdy i zdanlive zcela nesouvisejicimi, napr. z teorie cisel... Jak se rika: vse souvisi se vsim. Tvrzeni, ze zabyvat se teorii, ktera na prvni pohled nema prime prakticke pouziti, bych od studenta nebo dokonce absolventa VS rozhodne necekal :-(
To se pletete, software verifikovat jde, dokonce je to velky byznys, a formalni verifikace jsou docela v kursu. Chtel jste asi napsat ze nejde verifikovat KAZDY program- ale to nikdo nepotrebuje. Staci ze jde automatizovane testovat ze dany kod bude dodrzovat urcite invarianty, a dokazat ze nejaka tvrzeni o vztahu mezi vstupem a vystupem budou pravdiva pro libovolny vstup.
Ano, to je pravda, tak jsem to myslel - nelze verifikovat libovolny program.
Navic i pri psani programu se musi pocitat s tim, ze ho nekdo bude chtit verifikovat, ze treba existuje nejaka formalni specifikace atd. Jiste nejste schopen zverifikovat kdejaky zdrojak vam kdo podstrci a bude se ptat, co to dela, ci zda to dela to, co si mysli, ze to dela.
Myslím, že to dokázat lze, nicméně důkaz nejsem schopen napsat ;-(.
Vycházím z toho, že v mnoha ohledech je it. fce použitá pro výpočet Mandelbrotovy množiny podobná bifurkacím a tam opravdu nemůžete rozhodnout stav systému v budoucnosti. Jediná možnost je projít si postupně všechny stavy až do místa, které Vás zajímá.
To bych opravdu rád věděl jak to vyřešíte v konečném počtu kroků.
Ta otázka o typu dat je mimo (počítám v reálných číslech, konkrétní implementace na procesoru to samozřejmě převede na diskrétní hodnoty), dejme tomu že v long doublech. Tj. můžete si samozřejmě zkusit projít celý stavový prostor, ale na to zas nemáte dostatek paměti.
Jistě, že po nějakém počtu kroků můžete říct: už to diverguje (|z|>2), nebo možná zjistit cyklus (zase ne všechny), popř. pevné body, ale to je tak asi vše.
Jak například po 1000000 krocích zjistíte, že se jedná o cyklus o periodě 20000000?
OK
a ako toto riesenie obide problem spominany na zaciatku clanku?
void Q(void) {
if (halting_problem(Q))
while(1) { }
}
Tak co, zastavi sa funkcia Q alebo nie?
ZAKLADNY problem je, ze ak sa ta funkcia da naprogramovat, vznikne paradox a preto sa NEDA naprogramovat (neda sa naprogramovat tak aby riesila problem zastavenia pre vsetky mozne programy, co tvoja funkcia nerobi).
Mozna budu trochu (hodne) placat - je to davno, kdy jsem o tom neco mlhave slysel, ale pry teoreticti informatici vymysleli tridu problemu, ktere jsou neco jako "super neresitelne" (nebo jak se to jmenovalo). Jsou to takove problemy, ktere by nebyly resitelne, ani kdyby existovala reseni "obycejnych" neresitelnych problemu (napr. zminovany halting problem).
Dobre ze? (Vice viz kniha: tusim "Algorithmics - The Spirit Of Computing")
Teorie nezna hranic ;-)
V podstate ano - existuji problemy, ktere jsou neresitelne, i kdybychom meli orakulum, ktere by resilo halting problem. Jednoduse receno by se proste halting problem posunul o tridu vys - jedna se o tzv. relativizovany halting problem.
Kazdy program lze napsat jako primitivne rekurzivni predikat (pro laiky: jako primitivni formuli, nebo chcte-li program, ktery obsahuje nejvys elementarni funkce a omezene for-cykly, ale nikoliv while cykly), pred ktery se pripoji prislusny retezec kvantifikatoru (zde je vyznamne patrna souvislost s logikou). Podle slozitosti tohoto kvantifikatoroveho prefixu se zarazuje problem/program do patricne tridy aritmeticke hierarchie. Ta je shora neomezena a na kazdem jejim stupni je mozne najit problem, ktery je resitelny pouze s pouzitim silnejsiho vypocetniho prostredku (tj. vyssiho stupne hierarchie).
Doufam, ze to jako hrube vysvetleni staci.
Pěkné, a co víc, je to zcela jednoduše vidět:
Pokud bych si do jazyka přidal instrukci pro řešení halting problemu (nebo libovolného jiného v klasických jazycích neřešitelného problému), mohu udělat úplně stejnou konstrukci a halting problem pro tento nový jazyk bude zase v tom samém jazyce neřešitelný :-)
Inu, vševědoucí Pánbůh nemůže být algoritmem :-)
tak sem se pokusil ten program pro TS simulovat. tady je zdroj:
#include <stdio.h>
const int max_cycles = 65536 * 32767;
const int dotafter = max_cycles / 256;
const int tape_min = -32768 * 16;
const int tape_max = +32767 * 16;
int tape[-tape_min + tape_max + 1];
int pos = 0;
int state = 1;
int minpos = 0;
int maxpos = 0;
int getval() {
return tape[pos - tape_min];
}
void setval(int val) {
tape[pos - tape_min] = val;
}
bool terminate = false;
void goleft() {
if(pos>tape_min) {
pos--;
if(pos<minpos) minpos = pos;
} else {
printf("left -> out of range!\n");
terminate = true;
}
}
void goright() {
if(pos<tape_max) {
pos++;
if(pos>maxpos) maxpos = pos;
} else {
printf("goright() -> out of range!\n");
terminate = true;
}
}
int main(void) {
printf("br0\n");
for(int i = tape_min; i <= tape_max; i++) {
tape[i - tape_min] = 0;
}
bool terminate = false;
printf("br1\n");
int c = max_cycles;
printf("br2\n");
do {
switch(getval()) {
case 0:
switch(state) {
case 1:
state = 2;
setval(1);
goright();
break;
case 2:
state = 3;
setval(0);
goright();
break;
case 3:
state = 4;
setval(1);
goleft();
break;
case 4:
state = 5;
setval(0);
goleft();
break;
case 5:
state = 1;
setval(0);
goright();
break;
case 6:
state = 1;
setval(1);
goleft();
break;
default:
printf("0, 7 \n");
terminate = true;
}
break;
case 1:
switch(state) {
case 1:
state = 6;
setval(0);
goleft();
break;
case 2:
state = 4;
setval(0);
goright();
break;
case 3:
state = 5;
setval(1);
goright();
break;
case 4:
state = 4;
setval(0);
goleft();
break;
case 5:
state = 3;
setval(1);
goright();
break;
case 6:
state = 7;
setval(1);
goright();
break;
default:
printf("1, 7 \n");
terminate = true;
}
break;
default:
terminate = true;
}
c--;
if(c % dotafter == 0) {
printf(".");
}
terminate = terminate or (c <= 0 );
} while(not terminate);
printf(">>>>>>> %i\n", c);
printf("minpos = %i, maxpos = %i\n\n", minpos, maxpos);
}
ale nedospel sem k zadnemu reseni. po ukonceni (po vynulovani pocitadla - provedlo se 65536*32767=2 147 418 112 kroku) to skoncilo ve stavu:
minpos=-69975, maxpos=38, jelikoz testy s mensim poctem kroku skoncily min 'nalevo', predpokladam, ze jde o nekonecny cyklus...
v clanok vysvetluje ze vo vseobecnosti si programator nemoze byt isty ci napisal korektny (= necykliaci) program pretoze neexistuje algoritmus ktory by bol schopny toto rozhodnutie urobit.
u trivialnych programov (95% programatorskej praxe) dokaze clovek odhalit "pohladom" resp. metodou pokus omyl, ale u zlozitejsich ako napr schemu DES http://homel.vsb.cz/~ves064/Des_1024x768.html
clovek pohladom neodhali nic.
teda DES uvadzam preto lebo ma nedavno napadla idea si kdesi na nete najst popis DESu a ho aj implementovat ale ked som uvidel tu schemu tak ma velmi rychlo presla chut.
Jeden z dovodov bol aj ten ze na odsledovanie spravnosti medzi stavov by som musel tieto stavy pravdepodobne rucne pocitat :(
To není tak docela pravda: U většiny programů, které napíšu, vím, jak jsem na ten algoritmus přišel, a proto i dovedu sestrojit důkaz toho, že program je správně. Háček je ovšem v tom, že pokud program nevznikl takto, jeho korektnost se zjišťuje těžko a ve vší obecnosti to ani algoritmicky nelze.
(Docela hezký případ, který se mi už několikrát stal, je, že někoho napadne algoritmus řešící nějaký problém a když už ho má skoro naprogramovaný, uvědomí si, že k tomu algoritmu došel naprosto chybnou úvahou a není si najednou vůbec jistý, jestli ten algoritmus funguje ... a tak se snaží najít vstup, pro který fungovat nebude, a ono to nejde a nejde a nejde, až po několika hodinách se mu podaří dokázat, že to opravdu vždycky funguje, i když vůbec není na první pohled jasné, proč by mělo, a že to je daleko efektivnější řešení než nějaké evidentně korektní, které koho napadne na první pokus, když zrovna neudělá tu správnou chybu :-) ).
Ještě poznámka: Příznivci vývoje softwaru pomocí formálních specifikací (tj. nejdříve se sepíše formální specifikace problému v nějakém jazyce, pak se programuje a pak se dokazuje, že program opravdu řeší problém podle specifikace) nechť mi prominou, ale i když jsem u obvyklých jednoduchých problémů velkým příznivcem dokazování, u interaktivních systémů a podobných věcí si opravdu nemyslím, že by to byla ta správná cesta -- prostě proto, že u takových programů bývá chyba velmi často v tom, co si _myslíte_, že by program měl dělat, čili ve specifikaci ... a popsanou formální metodou zajistíte pouze to, že máte dokonale korektní implementaci nesmyslu :-)
Podle mne TS cykli a generuje posloupnost:
a[0]=3
a[1]=5
a[n]=a[n-1]+a[n-2]-n+2
nebo nejakou variaci na tohle tema. Ja tohle cislo ziskal jako pocet "hor" nebo "vrcholku", ktere TS nakresli pri simulaci pomoci sedu a kresleni pomoci stavu S1 ;-)
P.S. V clanku je asi preklep v tech sedovych pravidlech (pokud teda maji predstavovat ten puvodni TS), pravidlo cislo 10:
s/(S3)1/1(S5)/
(puvodne tam je misto S3 S5)
jeste jsem to nekontroloval, ale na chybu to opravdu vypada. Otazka vsak stale zustava: Co udela tento stroj:
0 1
-------------
(S1): (S2)1R (S6)0L
(S2): (S3)0R (S4)0R
(S3): (S4)1L (S5)1R
(S4): (S5)0L (S4)0L
(S5): (S1)0R (S3)1R
(S6): (S1)1L (S7)1R
(S7): Stop Stop
s nekonecnou - obousmernou paskou - v pocatku same nuly
Z vysledku jednoduche simulace je patrne, ze uvedeny
soutezni TS generuje nekonecnou posloupnost ...10101010101010..., ktera od pocatecniho stavu hlavy TS roste do nekonecna smerem v pravo i v levo a to podstatne rychleji doleva (tento TS se nikdy nezastavi). K jakemu ucelu a nebo co modeluje tento TS nevim.
Důkaz neřešitelnosti halting problemu, tak jak je podán v článku, je zjednodušený možná až moc, takže není úplně jasné, že je opravdu korektní. Funkce zastavi() potřebuje znát vnitřek testované funkce včetně všech dalších funkcí, které ta testovaná volá, k čemuž Céčková syntaxe moc nenavádí. Šlo by popsanou konstrukci zmodifikovat, aby místo funkcí předávala jejich zdrojáky, ale pak bychom museli ve funkci Q konstruovat zdroják funkce Q, což je sice pěkná hříčka (schválně si rozmyslete, jak by se to dělalo), ale je to zbytečná komplikace.
Korektně a snad srovnatelně srozumitelně by to šlo třeba takto:
Předpokládejme, že všechny funkce mají za parametry stringy a výsledkem funkce je zase jenom string. Dokážeme, že nelze naprogramovat funkci Halt(X,Y), která dostane za parametry X=zdrojový text nějaké funkce s jedním parametrem a Y=parametr pro tuto funkci a odpoví "ZASTAVI" resp. "NEZASTAVI", podle toho, zda X(Y) se zastaví resp. nezastaví.
Kdyby tomu tak bylo, lze zkonstruovat i funkci H(X), která zavolá zastavi(X,X) a zachová se přesně opačně (tedy pokud se funkce X na vstup rovný svému vlastnímu zdrojáku zastaví, pak H(X) se nezastaví a opačně). [Máme-li k dispozici zdroják funkce zastavi, vyrobíme z něj snadno zdroják funkce H.]
No jo, jenže H je také funkce jedné proměnné, takže jde zavolat na svůj vlastní zdroják, čímž uděláme totéž, co funkce Q v článku, a H se nemůže ani zastavit, ani nezastavit, což není možné.
Laskavý čtenář nechť si povšimne, že při konstrukci funkce H jsme nepotřebovali žádné speciální vlastnosti programovacího jazyka, jen to, že se v něm dají dělat podmínky a věčné cykly a skládat funkce. Proto i kdybychom si do jazyka přidali libovolně silné operace (a nezabývali se chvilku tím, zda jsou technicky realizovatelné -- pokud máte rádi matematiku, přimyslete si třeba možnost používat existenční kvantifikátory; původní halting problem by se pak snadno napsal jako "existuje x takové, že se simulace programu X zastaví po x krocích"), půjde udělat úplně stejná konstrukce a opět dokážeme, že i takovýhle silnější jazyk na nějaký problém nestačí.
Ještě odbočka: Samozřejmě by také šlo zkonstruovat jazyk, ve kterém by se všechny programy vždycky zastavily (třeba tak, že zavedeme povinnost před každým cyklem [rekurzivní volání je také cyklus] předem uvést, kolikrát se maximálně může provést, čili nahradit všechny cykly for-cykly). Jenže takový jazyk bude mít pro změnu jiné neřešitelné problémy, třeba v něm nepůjde napsat interpretr toho samého jazyka. A dokáže se to skoro stejně, jako jsme před chvílí dokázali neřešitelnost halting problemu:
Nechť I(X,Y) je interpretr funkcí s jedním parametrem, čili funkce, která pro zdroják X a parametr Y vrátí totéž, co X(Y). Pak existuje i Z(X)=I(X,X)+1 a pokud byla I for-cyklová funkce, je i Z taková (žádný cyklus jsme nepřidali). Jenže pak Z(Z) = I(Z,Z)+1 = Z(Z)+1 :-)
To jsme se dostali do pěkné šlamastyky, což?
Tak google snad pomohl .. turinguv stroj je (s velkou pravdepodobnosti) sestistavovy Busy Beaver?
Ted nemam cas hledat prislusny stroj, pokusim se vecer (taky lumparna prehazet stavy)
Pocet kroku - nejlepsi BB(6) ktery se mi podarilo najit, je :
B1R C0R A0L D0R D1R H1R E1L D0L F1R B1L A1R E1R
ones = 2,537,699,363,594,175,843,063
steps = 598,383,321,904,238,506,234,609,927,865,294,538,105
, takze pocet kroku bude velky ;-)
Moment, asi tomu nerozumim, ale podle http://mathworld.wolfram.com/BusyBeaver.html by sestistavovy busy beaver mel zapsat Sigma(6) jednicek, coz je > 1,29x10^865.
V te souvislosti me zaujalo, ze to je stroj, ktery zapise maximalni mozny pocet jednicek a zastavi se. Z toho by vyplyvalo, ze pokud mam n-stavovy TS, ktery uz zapsal vic, nez Sigma(n) jednicek, tak mam dokazano, ze se nezastavi?? [Fakt, ze to je 1. velke cislo, 2. nevycislitelna funkce pomijim.] Nebo v cem tomu nerozumim (myslim v teto konkretni malickosti, obecne do toho moc nevidim, ale to vim i bez vas :) ).
> Z toho by vyplyvalo, ze pokud mam n-stavovy TS, ktery
> uz zapsal vic, nez Sigma(n) jednicek, tak mam
> dokazano, ze se nezastavi??
Obavam se, ze ne. Do \Sigma(n) se pocitaji jednicky, ktere zbydou na pasce _po zastaveni stroje_, ne behem vypoctu. Vas n-stavovy TS muze vsechny zapsane jednicky zase smazat, a vesele skoncit.
Well done! :-) Akorat tech jednicek je trochu vic, teda presne:
12914951964730997250673433546819849509549358087128 69005395873005091204311405044485024013143268788877 96982050179592672794672477591595948221752253054324 81859864495796137909683447198447312843568880129905 33063069223512777765526485338267097939892666393404 33645541695093655408344618435778415742964338602689 29575034928793440722283883496539655948945100141899 42944746881736756960481303815091265680548717247559 30418437122794678536247499891470543037484990932498 45855395105658447844504456040960051641314951220524 82406177581463473827266448103006672709418626513574 98031478037424866640095921801194216728219139588401 23231130890028804306931645773916087727281493526404 73317019897976560342477660683368440952973000704411 85616248748736529970020326673445871378590029099788 72928814647043325481327200728882173015355211743620 25443804176796589274203597930628676364226731372114 6548318330807873 = priblizne 1.2*10^865
kroku se provede jeste o dost vice, neco kolem: 3.0*10^1730
nejnovejsi vysledky muzete videt na:
http://www.drb.insel.de/~heiner/BB/bb-6list
Teda, abych rekl pravdu, ani jsem nedoufal ze na to nekdo prijde, muzu vedet jak ses k tomu dobral? :-)
Btw, odmena je tvoje, napis cislo uctu me, pripadne johance a odmena bude na tebe presmerovana. Btw. v clanku jsem sliboval i pifo, bude-li prilezitost, urcite ti ho rad koupim :-)
Pocet jednicek:
ve skutecnosti jsem vygoogloval jen BB 'k', pro ktery cisla patri. Nejak jsem nemel cas hledat dal, prece jenom prace obcas nepocka.
Nalezeni:
Asi nejlip podle google query:
turing machine halting problem example
turing machine halting problem seven
six state busy beaver
six state "busy beaver"
"busy beaver"
BB je zminen nekde u turing machine, vhodny kandidat kvuli zamereni clanku(trivialne vypadajici problem), odpovedi v diskuzi(algoritmus se zastavi, nerealnost nalezeni reseni vypoctem). Podobnost teto TM s BB je celkem zrejma.
No a pak jsem se uz jen stazil najit prislusny BB, ale trosku jsem si to zkomplikoval tim, ze jsem predpokladal, ze jsi zlomyslne prehazel stavy.
Odmena:
Myslim, ze honorar za tento clanek ti pravem nalezi(a urcite si to nemyslim sam ... ctenost, pocet reakci).
Ale piva se nevzdam, jen nevim, kdy bude prilezitost.
Nechápu, o co autorovi článku šlo. Seznámit laickou veřejnost s problémem zastavení? Proč by to dělal? Buď veřejnost má zájem o podobné problémy a raději si najde srozumitelnější, přesnější a hlavně bezchybný text nebo o ně zájem nemá a pak pochybuji, proč by tento nesmyslný článek četla.
Už jenom to množství nepřesností či přímo omylů, které se v článku vyskytují.
Např. jeden z nejkřiklavějších (autor se to pokusil pojmout jako pohádku).
...
Tento pán byl velmi chytrý a jednoho dne vymyslel stroj a pojmenoval ho "Turinguv stroj"
...
Alan Turing byl, beze sporu, jeden z nejvýznamějších mužů tvořících moderní historii informatiky. Ale tvrdit o něm, že svůj matematický model pojmenoval po sobě, to už trošku silná káva... Turing sám popisovaný model nazýval a-machine (Automatic Machine) a název "Turing Machine" se ujal až mnohem později.
Tento a ostatní omyly v článku obsažené, pouze dokazují autorovu neschopnost psát skutečně výstižně a smysluplně. Napsat článek, kterému nerozumí ani laik, ani odborník, opravdu nemá význam.
PP
stačí vypnout komp a nebo věřit v pravděpodobnost chyby komponenty stroje a v konečnost zdroje energie + v konečnost universa.
Šťouralové prominou, ale každé známé nekonečno se stává konečnem a tedy:
konečno +d(konečno) = nové nekonečno.
Ovšem za chvíli i to nové nekonečno odhalíme a tak dále.
Doporučuji číst S. Lema, méně hulit trávu a nepsat nesmysly
Nechci vam brat iluze ale nekonecno zustava nekonecnem nezavisle na tom do kolika my umime vycislovat. Berte to tak ze mate-li souradnicovy system a vedete-li primku z bodu [0,0] do bodu [nekonecno,1], ta primka bude rovnobezna s osou x.
To co umime vypocitat je ale jen napodobenina kdy se snazime nekonecno necim aproximovat. Jestli je pro vas maximum cislo 3 nebo 30 - nebo 3.000.000.000 je jedno protoze ta primka rovnobezna nebude ani v jednom z tech pripadu. Tezko o ni muzete rict ze je min nebo vic rovnobezna - proste bud je nebo neni, boolovska hodnota.
Boze, v podstate z tohoto clanku vznika dalsi problem ... vybrat si ... hulit travu nebo psat clanky na root.cz ... autor toto asi neresil a kombinoval ... ach jo.
Nechcete zacit delat neco uzitecneho? Kopat prikopy nebo tak neco ? :p
imho fce pro zjisteni zda program dojde do konce nebo ne napsat lze. Pouze predvadena konstrukce zpusobi zacykleni. Stejne tak by se dalo zacyklit hodne veci. Ale to preci neznamena ze nejdou napsat!!!
Si tady pripadam jak jednou na hodine matematiky, kdyz nam matikarka neco dokazovala :
neco = necox protoze neco/2 = necox/2 .... atd. atd. a upravovala a upravovala nez dosla k neco = necox ... hmm ... peknej dukaz ... stejne to moc lidem nevadilo ...
Pro me je totiz dukaz neco ve tvaru 5=5 a ne nejakej zacyklenej haluz.
Bye.
a co hulis ty? funkce rozhodujici zda program skonci napsat NEJDE, coz v tom clanku, ackoliv neni nic moc, bylo vysvetleno docela dobre a v diskusi pod nim jeste lepe. byl naznacen formalni DUKAZ, takze tvoje "imho" nikoho nezajima - rekni kde je v tom dukazu chyba nebo mlc. je ok zes to nepochopil, ale proc sem teda pises blbosti? proste kdyz necemu nerozumis tak se k tomu nevyjadruj.
Nechapu ten druhy kousek kodu:
1 void Q(void) {
2 if (zastavi(Q))
3 while(1) { }
4 }
Proc ve fci Q testujeme na zastaveni sami sebe? Prece logictejsi by bylo testovat ve fci Q jinou fci, ne? Jinymi slovy, v tomhle kousku kodu nevidim dukaz, ze nejde napsat fci zastavi() (i kdyz to je asi pravda, ale z tohohle bych si to neuvedomil).
Muzete mi to prosim nekdo vysvetlit?
Diky.
Pro zajímavost Vám zděluji že programátoři yourdolphin, aisquared a freedom scientific. Všechny tito firmy které jmenuji sídlí v Ameryce programování odflákávají. Za podpůrné pomoci jednoho známého ajťáka jsem je dokázala z čista jasna prokouknout. programátoři yourdolphin flákají programování softwaru a reakce se projeví na grafice a to tak že 16bit a 32bit zmizí a je tam pouze 4bit a rozlišení to dá poloviční z nejnižšího možného a je to nežádoucí projev biosáckého původu. Aisquared to flákají způsobem že se nežádoucí reakce projevují různě např. napájení ale nedobjí se a pořád je to na 0% a po odpojení od proudu to chcípne(poznámka: vím to z vlastní zkušenosti protože jsem byla svědkem daného případu kterýž se stal spolužákovy ve škole). Opět je to chyba biosáckého původu. Firma Freedom scientific o které jsem vždy věřila že programování nefláká tak jsem dokonce jeden z jejich produktů jsem měla zájem vyzkošet. Po té jsem ve finále zjistila že programování taktéž fláká. Nežádoucí projevi jsem zažila osobně a to, že po formátování hárddisku to vypisovalo a nový čistý instalaci po probuzení z lehkého spánku S1 POS bylo vypsáno v oznamovací oblasti nejsou nainstalovány řadiče zvuku, po druhém uspání a probuzení se to zaseklo kurzor myši se hýbal ale na klikání to nereagovalo, po třetím uspání se to už neprobudilo. Nežádoucnost opět biosáckého původu. Další nežádoucnosti biosáckého původu bylo přebíjení. Když jsem to oznamovala firmě která je dovoscem daného softwaru a řekla co se stalo, a řekla jsem bohovskou pravdu tak mi ji odsuzovali. Tak od této chvíle už se na ně ani jednou neobrátím a na jejich produkty se radši vyseru. Nebudu je na nic upozorňovat a ať udělají časem vlastní zkušenost a po té jím bude jasný že odsuzovali bohovskou pravdu.
Shrnutí: Flákat programování softwaru a vypouštění software na svět který je naprogramovaný odfláknutě je přestupek a trestný čin. A všechny tři Americké firmy které jsem uvedla by zasloužili pár facek za to že programování odfláknou a po té to odfláknutý vypustí na svět.