Názory k článku Co je to nenaprogramovatelné?

S tim nekonecnym cyklem je to fama. Neexistuje pro to matematicky dukaz. Navic v praxi je to jedno, pokud se program sekne na hodinu, lze to uz povazovat za nekonecny cyklus.

No to je sice pravda, ale fama to uplne asi neni. Zabyvalo se tim uz moc moc lidi a neprisli na reseni (ani kladne ani zaporne), takze ...

No neviem, ale na prednaske som videl formalny dokaz ktory potvrdzuje
Algoritmicku neriesitelnost problemu o rozhodnuti zastavenia.
Takze dokaz existuje.

Problem zastaveni je neresitelny, coz plyne z formalniho dukazu sporem, ktery predvedl jiz Alan Turing. Neni resitelny ted a nebude resitelny ani za milion let.

S tim nekonecnym cyklem je to fama. Neexistuje pro to matematicky dukaz. Navic v praxi je to jedno, pokud se program sekne na hodinu, lze to uz povazovat za nekonecny cyklus.

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.

Někde jsem četl, že člověk (uživatel) nějakého běžného software, pokud třeba klikne a nic se neděje více, než 4 vteřiny, má s největší pravděpodobností sklony kliknout znova, či být velmi nervózní :-D Proto asi existují progressbary, aby nervozisti viděli, že se "něco děje" :-D

Skús otvoriť v notepade 4 GB súbor :-)

Dik, opraveno, jsem slepa a blba

Tak marš pryč z ROOTa, takový tady nepotřebujem! ;-)

V tomto bodě s Vámi souhlasím, ale stejně si myslím, že autorem článku je Ondřej Holeček a ne Johanka.

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 :-) ).

Co mas proti, sem s tim?
A jinak, myslim, ze potrebujete, jinak momentalne nemate clanky ani zpravicky :)

Johanka ma muj obdiv. Po Smrtakovi cokoliv opravovat je neco mezi sebemrskacstvim a sebemrskacstvim. Clanek jsem cetl jeste nez byl na rootovi a byla to sila ;))

Timto zdravim Smrtaka a dekuji za zajimavy clanek.

Vycislitelnost je veda krasna, lec jeste v ni zustava nekolik problemu nevyresenych. Snad se to podari rozlousknout v tomto stoleti.
Diky za pekny clanek. :-)

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.

Jestli si to jeste dobre pamatuju, tak ve vycislitelnosti existuje tzv. Halting problem, coz neni nic jineho, nez v clanku popsany jev :-)

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.

Dovolil bych si podotknout, ze mezi NP a problemem zastaveni (ktery neni vycislitelny) je priblizne stejny rozdil, jako mezi zidli a kridou. Predstavou, ze je to totez, by rozhodne nekdo, kdo netrivialni dobu pobyval na slusne skole v oboru informatiky, nemel trpet.

Jsi vedle jak ta jedle. Slysel jsem z tajnych zdroju, ze na Mendelu uz dokazali resit problem zataveni v NP. Dosali za to nejake penize a ted za ne stavi novou budovu. Ja to vim, ja jsem bydlel kousek od Mendelu, tam se nic neutaji. :)

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á

No Milane, to ses trosku ztrapnil, ne?
Jeste ze ctenari roota vetsinou netusi jake a hlavne odkud mas tituly ;-)

> (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.

Tam sice ne, ale tady ...

Mr. Milan Sorm
head of Institute for Informations and Informatics
Mendel University of Agriculture and Forestry
5 Zemedelska, Brno
Europe, Czech Republic

http://cinani.zacni.cz/doc/tabor01_dopis01.pdf

... ano :) Google to jisti :-D

Hezkej clanek, ale myslim, ze ho ocenim az se poradne na to cteni vyspim.

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)

Bezne se pouzivaji obe pojeti Turingova stroje - s pravostranne nekonecnou a oboustranne nekonecnou paskou. Lze pomerne jednoduse dokazat ze obe pojeti jsou ekvivalentni.

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...

... stroj s vice hlavami, vice paskami, ... s omezenym mazanim - se podle mého zastaví, protože se zadře :-)
A jinak díky za článek, alespoň se člověk vrátí zase na zem a zjistí, že vlastně z těch počítačů nerozumí skoro ničemu.

turingov stroj s nekonecnou paskou a s jednosmerne nekonecnou paskou je rovnako silny

Turing byl skutecne genius. Za valky ho anglicani potrebovaly (nasel zpusob jak desifrovat Enigmu i bez operatorske chyby opakovani sifrovaneho klice zpravy). Po valce byl nepohodlny, byl totiz 4%. Skoncil sebevrazdou, jedem.....

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 :-)

Myslim, ze bombu vytvorili Polaci. Viz ukazkove kapitoly z teto knihy na www.scienceworld.cz

A mimochodem, Turing se sice otravil, ale v te dobe uz zil v Americe

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 :[]

Bohuzel, function not implemented :( Je to hardcoded v mozku.

Z teplých krajin přiletěl WarFTPd server - http://www.jgaa.com/. Ty gayové jsou ňáký schopný. :-)

lolec :-)))

No vidis, a ja si myslel, ze sendmail napsal nejaky blazen! ;-)

co 4%, ale mezi 'game developers' je prej 15 overenejch pripadu zmeny pohlavi. Urcite se to da dohledat googlem (Dan Bunten x Danielle Berry (skvely M.U.L.E. na 8bitech), William Mataga x Cathryn Mataga, sef(ova) Makromedie tusim...)

studenej Jindroush

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í).

Treba tu:
ftp://ftp.linux.cz/pub/linux/gentoo/distfiles/gturing-0.1.1.tar.bz2

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.

uz kulhanek to pouzil vo vladcoch strachu, ale nemam nanho kontakt aby som sa spytal...
;o)
dik,
a.

Nehledej nic složitého... Pumlíč je prostě balón :) (třeba kopačák).

mimochodem "pumlíč" je tak běžné slovo, že je dokonce v seznamu povolených slov pro scrabble.
Jestli se nepletu, tak jsem jej viděl v Klabzubově jedenáctce.

"Je to v seznamu povolených slov pro scrabble" nelze jako důkaz běžnosti slova použít. Tato výčtem definovaná množina (nazývaná BLEX) obsahuje tisíce neběžných slov a na druhou stanu v ní chybí několik slov běžných.

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/

jo a právě jsem našel, že už o něm mluvil werich
http://werich.poda.cz/news.php?topicid=79&action=add

Hovorový výraz, staršího data. Nikdy jsem ho myslím neslyšel vyslovit, vždycky jsem ho jenom někde četl. (Jsem z Moravy, možná proto.) Mně se vybaví laciný gumový balón, tedy spisovně míč, po slovensky lopta, maďarsky tuším labda.

Vyhlasuji soutez.... Venuji honorar za tento clanek tomu, kdo sem jako prvni napise, co udela TS zminovany v tomto clanku jako priklad. (trva do posledniho ledna, pak si honorar necham sam!) Rada: google je mocny!

Stroj pobezi donekonecna a bude pasku viac menej rovnomerne pokryvat nulami a jednotkami. Okrem toho bude mat tendenciu posuvat sa dolava. ("Popisana oblast pasky sa bude smerom dolava rozsirovat rychejsie ako doprava). Na nekonecnej paske to je ale jedno :)

ee, tak to neni :-)

lolec :-)))))

Přiznávám se bez mučení, že mi to celé připadá jako blábol a že funkci zastavi bych určitě naprogramoval a to dokonce na 3-4 řádky, ale možná jsem jenom nepochopil co tím chtěl básník říci (čili uznávám vlastní blbost ;))

to by me zajimalo :) tak sem s ni ;)

<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. :)

program() { for(i=0;;i++) pamet[i] = 1; }


kdy se program dostane do nejakeho stavu 2*? Po kazdem kroku bude v pameti neco jineho, kazdy krok je jiny stav. Nebo se pletu?

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.

Výborně, to se mi hodí :-) Už dlouho dělám prográmky počítající různé fraktály. Vezmeme si tedy například Mandelbrotovu množinu. Ta je vytvořena z bodů, pro které posloupnost komplexních čísel z

Undefined global symbol halting_problem. Program nelze linkovat, tedy ani spustit, tedy ani rozhodnout o jeho konečnosti.

predmet Formalni jazyky a automaty
na FI MU by te naucil:o)

http://www.fi.muni.cz/usr/kretinsky/fja1.html

hehe, to jo ;-)

to byly zážitky, nebo Motyčková - vyčíslitelnost a složitost!!

Asi tak.
A reseni principialniho problemu v sirsi rovine je spis otazka umele inteligence.

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 :-)

Receno pekne, elegantne a vtipne :-) Dik, mj.

Strasne mi to pripomina logiku a hlavne Godela a jeho vety o neuplnosti.

Jo jo, však také důkaz neřešitelnosti halting problemu a důkaz Gödelovy věty o neúplnosti jsou, odhlédneme-li od technických detailů (které u neúplnosti jsou docela nechutné), vlastně totéž.

Dá se ukázat, že pokud by byl Pán Bůh vševědoucí, tak neplatí matematická logika :-) Vyšlo to relativně nedávno v informagice. Důkaz se provádí sporem.

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...

zase vedle, tohle neodsimulujete, na tohle vam pomuze bud velmi chytra hlave, a nebo google ;-)

Naprosto nechapu o cem mel tenhle clanek byt, co chtel dokazat, a cim mi mel prispet. Pritom by stacilo jen par vet na zacatku ktere by to treba objasnili pro debily jako sem ja. :) Fakt nechapu vo co go, sem uplne mimo, a to uz sem 2 dny strizlivy...

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 :-)

Cao. Mam za to, ze priklad skonci po 57 krocich ve stavu 010101011. I kdybych mel nahodou pravdu, hororar si zaslouzit ty.

Tak ne, omyl, odvolavam :)

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)

Nevím co řešíte, když se program nemůže zastavit , tak tu máme přece čudlík na restart či vypnutí počítače.
Opravdu nechápu o co Vám všem GO !

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ž?

Co k tomu dodat? To je tak dobře napsané, že to pochopí i elektrikář z VUTu :-D. Díky.

Jen se nepodceńuj :). Ty mezi námi elektrikáři (lhostejno zda slabo- či silno-) přeci jen vynikáš a nemůžeš být brán za etalon "průměrného VUŤáka".

Nazdar soumare ;) Sem z toho jelen

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.

sry, zapomel jsem se podepsat... hlava derava...

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.

Problem zastavenia pre standardne sxemy nie je rozhodnutelny, je vsak ciastocne rozhodnutelny!!!
V pripade uvazovania schem strukturovanyx snad postaci tvrdenie, ze trieda standardnyx sxem je silnejsia ako trieda strukturovanyx

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.

> Proc ve fci Q testujeme na zastaveni sami sebe?

Protože chtěli dokázat že funkce Q() a zastavi(Q) nemohou běžet ve stejné exekuční doméně. Omylem to ale považují za důkaz neexistence jedné z nich.

> Prece logictejsi by bylo testovat ve fci Q jinou fci, ne? Jinymi slovy, v tomhle kousku kodu nevidim dukaz, ze nejde napsat fci zastavi()

Zcela správně. Je to podobný nesmysl jako chtít po všemocném Patejlovi balvany tak velké že je neuzvedne a ze vzniklého paradoxu vyvozovat jeho neexistenci :)

> Ukažme si, že funkce Q je nesmysl. A protože jediné sporné, co v této funkci používáme, je funkce zastavi, ukážeme tím i, že ona funkce zastavi je vlastně nesmysl.

Jablka + Hrušky = nesmysl. A protože jablka jsou v pořádku, musejí být nesmyslem hrušky. Na vysvětlení že v pořádku mohou být současně jablka i hrušky, a nesmyslem je pouze jejich sčítání, autor asi zapoměl.

turingovym pohledem existuje jednoduchy prehledny algoritmus
pro hru sachy ktery je ale prakticky nepouzitelny. Jeho casova
narocnost pro realne pocitace je ohromna.Nebo take casove exponencialne algoritmy prakticky nepouzitelne.Zijeme ve svete
omezenych zdroju coz matematici casto zanedbavaji (t.j. abstrahuji).

Az nekdo bude chtit rikat ze funkce pro zjisteni konecnosti muze existovat, at tim prozene tenhle pseudokod:

while(ziskej_stisknutou_klavesu() != 'a');

jestli neco zjisti jestli tenhle "program" skonci, tak je to fakt dobrej program ;)

V případě programů se vstupem od uživatele přece musí být parametrem funkce zastavi() i množina vstupů.

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.