border=0

Foarbyld 10.4

In Turing-masine is in formele systeem dat in soad fan syn konfiguraasjes generearret. It boarneobjekt is de earste konfiguraasje; regels - in funksjoneel tafel. De eardere fan 'e fertsjintwurdiging fan algoritmen yn ferskate algoritmyske modellen waard lykwols earder (f. 7) bewiisd. Dêrom, as it algoritme yn 'e fertsjintwurdiging fan de Turing-masine in formele systeem is, dan feroaret de algoritme yn elke oare representaasje ek in formele systeem. Tagelyk is de konversaasje ("elke formele systeem in algoritme") is ferkeard - de reden foar dizze omstannichheid sil gewoaner wurde as it besprek fan de eigenskippen fan formele systemen.

De foarbylden sjen litte sjen dat formele systemen tige ferskille binne. Lykwols, lykas yn 't gefal fan algoritme, in tal mienskiplike eigenskippen dy't alle formele systemen besitte kinne kinne ûnderskieden wurde.

1) diskriminaasje. Dit eigendom fan formele systemen is manifestearre, earst yn it feit dat de komponenten fan it systeem bestean út unveilige eleminten (objekten); Tsjintwurdich is it feit dat it oantal regels foar it opbieden fan nije objekten fan besteande persoanen finite is.

2) Fermogen. It essinsje fan 'e formele oanpak is om in oantal prinsipes te folle (observearje):

- Prinsipe fan pedantry: alles dat dien is, wurdt stringend dien neffens de regels fan it formele systeem. As it formele systeem net de winske objekten biedt binnen de besteande regels, dan is it ûnmooglik om te bouwen, de regels te brekken. Jo kinne besteande regels feroarje of nije ynfile, mar dit is lykwichtlik it bouwen fan in oare formele systeem;

· It begjinsel fan eksplisite beskriuwing: alle betingsten foar it tapassen fan de regels en de aksjes dy't útfierd wurde as se tapast wurde, wurde eksplisyt formulearre. De wurdearring en beskriuwing fan 'e aksjes moatte de kennis en ûnderfining net brûke fan' e kontraktor of de "standert aksje", d. wat net eksplisyt beskreaun, mar ymplisyt. Yn 'e praktyk om sokke strieze beskriuwing te bouwen as it slagget, dan bliuwt it tige omslach. Hâld it lykwols streng en konsekwint as optionaal: as de útfiner in persoan is, dan kinne jo earst de needsaaklike kennis foar him passe en dêrnei opje; As de útfierer in apparaat is, wurdt de detail fan 'e beskriuwing bepaald troch it besteande systeem fan kommando's.

It prinsipe fan syntaksis: de betingsten foar it tapassen fan de regels wurde allinich formulearre mei help fan gewoan eksterne en dúdlik ûnderskate funksjes fan dy objekten dêr't dizze regels tapast wurde (dêrom is diskriminaasje wichtich - de ferskillen moatte net lyts wêze oant ûntefreden). Mei oare wurden, de regels tapasse, is it genôch om allinich de eksterne eigenskippen fan objekten te ûnderskieden: har elementêre komposysje (symboalen, sifers, ensfh.) En har gegienlike arranzjeminten. Sokke eigenskippen yn 'e teory fan formele systemen wurde syntaktysk neamd . Dêrom kin it prinsipe in oare formulaasje krije: objekten wurde oars as beskôge as en allinich as sy ferskillend binne syntaktysk, d. In oare ferskil hawwe. Mei dizze oanpak is der gjin needsaak foar de begripen fan "signifikante ferskillen" en "lytse ferskillen" - se binne noch - en dan binne se ferskillende objekten, of se binne net - dan binne de objekten identike. Der is ek gjin konsept fan ynterne ferskillen dy't gjin dúdlike eksterne manifestaasjes hawwe: "kwea - goed", "hoewol - solid", "mei in komplekse ynterne boustruktuer - mei in ienfâldige struktuer". It is it begjinsel fan syntaksis dat it syntaktyske analyze fan 'e presinte-tekst makket. Syntaktysk korrekt tekst is de tekst dy't útfiert yn dizze formele grammatika, en wy litte gjin tekst sjen dy't syntaksisfrages befettet. Dizze analyze wurdt útfierd as it oersetten fan in kompjûterprogramma fan in programmearjende taal yn masine koades.

3) elemintêre aksje. It punt is dat alhoewol't de regels fan it formele systeem de meast ferskaatlike foarmen hawwe, kinne lykwols elke komplekse regel nei in ôfwikseling fan ienfâldige kombinatoriale manipulaasjes mei eleminten fan it systeem dy't fan meganyske aard binne. Yn 'e teory fan algoritme binne dizze manipulaasjes al besprutsen; As jo ​​op formele systemen tapast wurde, soart it folgjende set fan elemintêre aksjes:

It ferfangen fan in lege elemint (dat is in plak wêr't, neffens de regels, in elemint wêze kin, mar is net fûn) in net-lege elemint, dat lykweardich is foar it ferskinen fan in elemint neist de besteande;

It ferfangen fan ien elemint troch in oar (of in groep fan oaren);

In elemint wiskje (dus it mei in lege elemel te ferfangen).

Alle hannelingen fan it systeem fan kommando's fan 'e útfierer kinne lêst lestich wurde oan' e oanjûne elemintêre, dy't yn 'e teory fan algoritmen sjen litten wurde.

4) Opsjoneel determinisme. Dizze eigenskip bestiet út it feit dat op elke stap fan it proses fan nijbou opbouden, yn 't algemien gjin ien regel is tapast, mar ferskate, en dêrom wurdt de folgjende stap selektearre út ferskate mooglikheden. Dit is it ferskil tusken formele systemen en algoritmen wêrby't mar ien regel jildt oan alle generearre objekten (dit is in eigenskip fan it determinisme fan 'e algoritme), dy't de ienichheid fan it wurk ensuelt en it resultaat fan' e algoritme. It sil fair wêze om te sizzen dat in formele systeem mei ien regel by elke stap fan operaasje in algoritme is, en dêrtroch in formele systeem in algemien begryp is as in algoritme, en in algoritme kin beskôge wurde as in spesjale case fan in formele systeem. Yn it formele systeem is it mooglik om ferskillende regels te brûken (dit kin sjoen wurde fan de foarbylden dy't beskreaun binne boppe - skeakel of formulebou), dy't de generaasje net in inkeld resultaat (lykas yn 'e algoritme) soarget, mar in protte resultaten (bygelyks, Schach, in protte aritmetyske formulas).

Wat de algemiene eigenskippen fan formele systemen beskôge wurdt, is it nedich om wat mear oan te dwaan.

It formele systeem funksjonearret stringend neffens har regels en ûnderskiedt syn objekten allinich troch syntaktyske funksjes. Ut dit perspektyf beskiedt it unike in bepaald wiskundige model. Mar as it gebrûk fan dit model om elke probleem te learen, wurde spesifike eigenskippen en funksjes tawiisd oan de eleminten fan it formele systeem, d. it systeem wurdt ynterpretearre . In fergelykbere meganisaasje wurdt breed brûkt yn programmearjen: in proses wurdt ûntwikkele dy't soarget foar it útfieren fan in bepaalde ôfwikking fan de databesferwurkingshannelingen mei formele parameter (dat is in skema, in ferwurkingssparse is oantsjutte), en dus as in proseduere neamd wurdt, ynstee fan de formele, binne de wurklike wearden ferfongen. Itselde formele systeem kin ferskillende ynterpretaasjes hawwe, ôfhinklik fan it ûnderwerp wêryn it model brûkt is, of op 'e doelen wêrfoar't it makke is. Bygelyks foar in formele systeem dat beskriuwt de wetten fan wiskundige logika, is in oare ynterpretaasje - de regels foar it funksjonearjen fan logyske sirkels, dy't earder besprutsen binne.

Ynterpretaasje is in eksterne proseduere yn relaasje ta it formele systeem en wurdt net besprutsen yn it systeem sels. It nivo fan ynterpretaasje - it wurdt it meta-nivo neamd - kin formalisearre en ynformele wurde. Op it metaalvel is it systeem net >





Sjoch ek:

Foarbyld 9.4

Elke algoritme kin definieare wurde troch middel fan in turingfunksjonele diagram en ynfierd yn 'e oerienkommende Turing-masine.

Besykje fragen en taken

Besykje fragen en taken

De hierargy fan datastrukturen op eksterne media

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info