
key-tuchchh sett

ganit mein, praakritik sankhyaon key ack samooh koo key-tuchchh samooh kahaa jaataa haye yadi isake praarambhik khandon koo dwiaadhaari string key roop mein dekhaa jaataa haye tou unakaa varnan karna aasaan haih upsarg-mukt kolmogorov jatilata yathasambhav cumm haye, joe ack computable sett key karib haye. soloway ney 1975 mein saabit kiya kii ack sett ganana yogya honey key binaa key-tuchchh hoe sakata haye.
schnor-levin pramey kaa kahana haye kii yaadrichhik samuchchay mein praarambhik khand kii jatilata adhik hoti haye. iss prakaar key-tuchchh yaadrichhik seey bahut door hain. yahee kaaran haye kii inn seton kaa adhyayan algorithmic yaadrichhikta key kshetra mein kiya jaataa haye, joe computability siddhant kaa ack upakshetra haye aur computer vigyaan mein algorithmic soochana siddhant seey sambandhit haye.
usee samay, key-tuchchh sett computable key karib hain. udaaharan key liye, way sabhi atee nimn hain.ee. aise sett jinka turing jump rukane kii samasya seey ganana yogya haye, aur ack turing aadarsh banaata haye, i.ee. turing join key tahat seton kaa varg bund hoe jaataa haye aur turing reduction key tahat neeche kii or bund hoe jaataa haye.
paribhasha.
maanaa kii k upsarg-mukt kolmogorov jatilata haye, i.ee. ack string x diye jaane parr, k (x) ack upsarg-mukt saarvbhaumik machine key tahat input string kii cumm seey cumm lambai kaa output detaa haye. aisee machine, sahaj roop seey, ack saarvbhaumik prograaming bhasha kaa pratinidhitva karati haye jisamen aisee sampatti hoti haye kii kissy bhee vaidh prograam koo kissy anya vaidh prograam key uchit vistaar key roop mein praapt naheen kiya jaa sakata haye. key kii adhik prishthabhoomi key liye, ee dekhein.jee. chattin kaa nirantar.
humm kahate hain kii praakritik sankhyaon kaa ack samooh sthiraank b ω sootra _ 1 key madhyam seey k-tuchchh haye yadi
ack sett key-tuchchh haye yadi yeh kuchh sthiraank key madhyam seey key-tuchchh haye.
sankshipt itihas aur vikas.
key-tuchchata key vikas key shuruati dinon mein, key-tuchchh sett aur computable sett key prithakkaran parr dhyaan diyaa gayaa thaa.
chattin ney apane 1976 key pepper mein mukhya roop seey aise seton kaa adhyayan kiya kii b ω sootra _ 1 maujood haye.
jahan see saade kolmogorov jatilata koo darshaata haye. inn samuchchayon koo see-tuchchh samuchchay key roop mein jaanaa jaataa haye. chattin ney dikhaaya kii way ganana yogya seton key saath mell khaate hain. unhone yeh bhee dikhaaya kii key-trivial rukane kii samasya mein ganana yogya hain. iss varg key samuchchay koo aamtaur parr ankganitiya padanukram mein sootra 5 samuchchay key roop mein jaanaa jaataa haye.
robbert aim. soloway ack gair-computable key-tuchchh sett kaa nirmaan karane vaalaa pahala thaa, jabaki ganana yogya roop seey ganana yogya iss tarah key ack key-tuchchh key cummer dwara callood, coles aur anya aprakaashit nirmaanon dwara prayaas kiya gayaa thaa, aur key sett key liye ack nimn key bahut cumm thaa.
vikas 1999-2008.
gananashilata siddhant key sandarbh mein, ack laagat falan ack ganana yogya falan haye.
sootra 5 key ack ganana yogya sanniktan sootra key liye "a" sett, iss tarah kaa ack kaary charan s parr sanniktan koo a (n) mein badalane kii laagat "c" ("n", s ") koo maapata haye. pahala laagat samaroh nirmaan kuchera aur tervision key kaaran thaa. unhone ack ganana yogya samooh banaaya joe martin-loaf-yaadrichhikta key liye cumm haye lekin ganana yogya naheen haye. unakaa laagat kaary anukuli thaa, jisamen laagat kaary kii paribhasha sootra _ 5 sett key ganana yogya anuman parr nirbhar karati haye.
ack key-tuchchh ganana yogya gair-ganana yogya sett kaa ack laagat kaary nirmaan pahali baar down aur anya mein dikhaai diyaa.
humm kahate hain kii ack sootra _ 5 sett "a" ack laagat falan kaa paalan kartaa haye "c" yadi ack, sootra _ 11 kaa ack ganana yogya anuman maujood haye.
sootra _ 12 jahan sootra _ 13
aur sootra _ 14 ack nishchit saarvbhaumik upsarg-mukt machine sootra _ 15 key computable sanniktan mein "s"-th charan haye.
ack gair-computable key-tuchchh sett key nirmaan kaa rekhaachitra.
vaastav mein sett koo turant saral banaaya jaa sakata haye. vichaar twarit saralata aavashyaktaon koo puuraa karna haye,
saath hii laagat koo cumm rakhane key liye. hamein seema shart koo puuraa karane key liye laagat kaary kii aavashyakta haye
arthaat x key liye laagat key charanon parr sarvochata 0 hoe jaati haye jaise-jaise x badhata haye. udaaharan key liye, maanak laagat kaary mein yeh guna haye. nirmaan anivarya roop seey taba taka prateeksha kartaa haye jaba taka kii laagat cumm naa hoe jaae, formula _ 18 mein sankhya daalane seey pahale twarit saral aavashyaktaon koo puuraa karane key liye. humm ack ganana yogya ganana sootra _ 19 koo iss tarah paribhaashit karate hain kii
sootra _ 20. charan "s"> 0 parr, pratyek "e" <"s" key liye, yadi sootra _ 21 abhee taka puuraa naheen huaa haye aur "x" ≤2 "e" maujood haye jaise kii sootra _ 22 aur sootra _ 23, tou humm sootra _ 24 mein "x" daalate hain aur ghoshit karate hain kii sootra _ 21 puuraa huaa haye. nirmaan kaa anta.
yeh satyaapit karane key liye kii nirmaan kaary kartaa haye, pahale dhyaan dein kii "aeye" laagat kaary kaa paalan kartaa haye kyonki pratyek aavashyakta key liye adhikatam ack sankhya "aeye" mein pravesh karati haye. isaliye yog "s" adhikatam haye.
doosara, pratyek aavashyakta poori kii jaati haih yadi sootra _ 27 anant haye, iss tathya seey kii laagat falan seema kii shart koo santusht kartaa haye, tou kuchh sankhya koo antatah aavashyakta koo puuraa karane key liye ack mein ginaa jaayega.
samatulya charitra varnan.
key-tuchchata kuchh computational lones dhaaranaon key saath mell khaati haye, yeh kahate hue kii ack sett computable key karib haye. nimnalikhit dhaaranaaen seton key ack hii varg koo pakadati hain.
key" key liye lones.
humm kahate hain kii "a" "k" key liye cumm haye yadi "b" ω sootra _ 1 aisaa haye kii
yahaan sootra _ 30 aurecal sootra _ 31 key saapeksh upsarg-mukt kolmogorov jatilata haye.
martin-loaf-yaadrichhikta key liye lones.
aeye martin-loaf-yaadrichhikta key liye cumm haye yadi jaba bhee jaid martin-loaf yaadrichhik haye, tou yeh pahale seey hii "aeye" key saapeksh martin-loaf yaadrichhik haye.
martin-loaf-yaadrichhikta key liye aadhar.
"aeye" "martin-loaf-yaadrichhikta key liye ack aadhar haye yadi" "aeye" "kuchh sett" "jaid" "key liye" "jaid" "key liye cumm kiya jaa sakata haye joe" "aeye" "key saapeksh martin-loaf yaadrichhik haye.
key-tuchchata key adhik samatulya charitra varnan kaa adhyayan kiya gayaa haye, jaise kih 
2008 key baad key ghatanakram.
2009 seey, vishleshan seey avadhaaranaon ney charan mein pravesh kiya. isase kuchh kukhyaat samasyaon koo hull karane mein madad millie.
ack kaa kahana haye kii ack sett y ack sakaratmak ghanatva bindu haye yadi pratyek prabhaavi roop seey bund varg jisamen y hotaa haye, mein y parr sakaratmak cumm lebsug ghanatva hotaa haye. bnvenu, holzl, miller aur naaiz ney dikhaaya kii ack ml-yaadrichhikta apoorna haye yadi yeh ack sakaratmak ghanatva bindu haye. dinn aur miller ney iska upayog ml-cupping samasya key sakaratmak uttar key liye kiyaah pratyek martin-loaf yaadrichhik sett jaid key liye aeye key-tuchchh iff haye jaise kii ack ωz thaharaav samasya kii ganana kartaa haye, pahale seey hii jaid swayam rukane kii samasya kii ganana kartaa haye.
ack kaa kahana haye kii ack sett y ack ghanatva-ack bindu haye yadi pratyek prabhaavi roop seey bund varg jisamen y hotaa haye, mein y parr labsgue ghanatva 1 hotaa haye. koee bhee martin-loaf yaadrichhik sett joe ghanatva-ack bindu naheen haye, pratyek key tuchchh sett kii ganana kartaa haye joe bayenvenu, aadi dwara nirdhaarit kiya jaataa haye. dinn aur miller ney dikhaaya kii martin-loaf yaadrichhik sett haye joe ack sakaratmak ghanatva bindu haye lekin ack bindu ghanatva naheen haye. iss prakaar ack apoorna aisaa martin-loaf yaadrichhik sett haye joe pratyek key-tuchchh sett kii ganana kartaa haye. yeh sakaratmak roop seey pahale stephen dwara poochhi gaee aavaran samasya kaa jawab detaa haye aur phir miller aur naaiz dwara prakaashit kiya jaataa haye. saransh key liye dekhein l. bnvenu, aeye. dinn, aine. greenberg, aeye. kusera, jey. miller, aeye. neez, aur dee. turetsky.
key-tuchchata key roopon kaa adhyayan kiya gayaa haih

