Completamenti calcolabili di funzioni incalcolabili

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Completamenti calcolabili di funzioni incalcolabili

Data una funzione parziale $\phi$, diciamo che essa ha un completamento calcolabile sse esiste una funzione calcolabile totale $f$ tale che $(\forall x \in \mathbb N ) [\phi(x) \downarrow \; \Rightarrow f(x) = \phi(x)]$.

Esibire una funzione parziale non calcolabile che ammette un completamento calcolabile.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...

Nihilus

Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05

Nihilus ha scritto:Esibire una funzione parziale non calcolabile che ammette un completamento calcolabile.

Tra i tanti modelli equivalenti del concetto di computabilità, scegliamo di intendere ogni funzione calcolabile $f : \mathbb{N} \to \mathbb{N}$ come un programma che preso in ingresso un naturale $x \in \mathbb{N}$, o termina e restituisce un naturale $y \in \mathbb{N}$, in tal caso scriviamo $f(x)\! \downarrow$ e $f(x) = y$, oppure non termina, in tal caso scriviamo $f(x) \!\uparrow$. Inoltre osserviamo che esiste una biezione calcolabile, con inversa calcolabile, tra l'insieme delle coppie funzione calcolabile-ingresso $(f,x)$ e l'insieme dei naturali $\mathbb{N}$, pertanto identifichiamo questi due insiemi e diciamo che $c \in \mathbb{N}$ termina, risp. non termina, se la biezione associa $c$ ad una coppia $(f,x)$ tale che $f(x) \!\downarrow$, risp. $f(x) \!\uparrow$.

È ben noto che la funzione
$$H : \mathbb{N} \to \mathbb{N} : x \mapsto \begin{cases} 1 & \text{ se } x \text{ termina} \\ 0 & \text{ se } x \text{ non termina} \end{cases}$$
non è calcolabile. Definiamo la funzione parziale $\phi := H \upharpoonright H^{-1}[0]$, ovvero $\phi(x) = 0$ per ogni $x \in \mathbb{N}$ tale che $H(x) = 0$ e $\phi$ non è definita per ogni altro argomento. Chiaramente la funzione costante $\mathbb{N} \to \mathbb{N} : x \mapsto 0$ è un completamento calcolabile di $\phi$. Proviamo che $\phi$ non è calcolabile. Se per assurdo $\phi$ fosse calcolabile allora per ogni $x \in \mathbb{N}$ potremmo calcolare $H(x)$ come segue: eseguiamo in parallelo i programmi $\phi(x)$ e $x$, necessariamente uno dei due deve terminare, se termina $\phi(x)$ allora $H(x) = 0$, se termina $x$ allora $H(x) = 1$. Ma $H$ non è calcolabile, assurdo.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."

fry

Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Completamenti calcolabili di funzioni incalcolabili

Giusto!
Sostanzialmente è la stessa soluzione che ho pensato io, ma per dare un'idea di come può venire in mente la scrivo. Ho sempre trovato molto istruttive le dimostrazioni che partono dalla conclusione e risalgono passo passo alle premesse.

Cerchiamo di trovare la funzione "più facile" che soddisfi i requisiti: le funzioni calcolabili più facili sono le costanti quindi è ragionevole condensare l'incalcolabilità della funzione parziale nel suo dominio, cercandola costante là dove è definita.

Un teorema ci assicura che i domini delle funzioni parziali ricorsive sono tutti e soli gli insiemi ricorsivamente enumerabili. Quindi non ci serve altro che trovare l'esempio più facile di insieme non ricorsivamente enumerabile.

Il cosiddetto "teorema di complementazione" stabilisce un legame tra insiemi ricorsivi e ricorsivamente enumerabili: $A \subseteq \mathbb N$ è ricorsivo se e solo se $A$ ed il suo complementare $\mathbb N \setminus A$ sono ricorsivamente enumerabili.
Quindi basta trovare l'esempio più facile di insieme ricorsivamente enumerabile non ricorsivo e considerare il complementare.

È ben noto che l'insieme più facile che soddisfa questi requisiti è il cosiddetto "halting set" $K=\{ \langle i, x \rangle \, | \, \mbox{il programma } i \mbox{ si arresta sull'input } x \}$, ergo $\mathbb N \setminus K$ è l'insieme cercato.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...

Nihilus

Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05

BLACK GUCCI HAT

Also consider how you want your logo or company name BLACK GUCCI HAT emblazoned on a wholesale cap. While screen printing is less expensive, it doesn't wear well. If you can find an experienced wholesaler who will also do custom embroidery, you'll make a better impression and your logo will never fade or wear away.Water Bottles Are Used By EveryoneYou don't have to be an athlete these days to need a water bottle. With more people than ever aware of the need to stop using disposable water bottles, you can't go wrong with a good quality water bottle. Emblazoned with your logo, those water bottles will show up everywhere you can imagine. They'll be seen in gyms, boardrooms, class rooms, and at public events, spreading the word about your company.

You may already have special discounts for ski lifts, discount coupons, and other standard marketing tools, but so does every other resort. Offering free gifts such as wholesale hats to each of your guests is a great way to stand out from the crowd.Wholesale Hats, Gloves and Mittens As GiftsGiving a gift to your guests is only as successful as the quality of the gift you BLACK TRUCKER HAT choose. Typical marketing standbys like imprinted pens or plastic water bottles won't make an impression, but wholesale caps can capture your guests' attention in style. Almost everyone can remember losing a hat or gloves when they've gone skiing, snowboarding, or sled riding. If you order wholesale caps that are stylish and warm, you can offer each guest a lovely and practical gift they're sure TRUCKER HAT to use during their stay and long after they return home.

Why? Because they may not be skiing when they get home, but winter weather can linger for months.When your guests check-in, you can offer them their choice of hats from a collection that includes a variety of colors to match almost any winter coat or ski jacket. If you prefer to put gifts in the guest rooms, you may want to order matching scarves or mittens when you order your wholesale hats. When guests check-in, a lovely scarf and hat will be one of the first things they see in their room. Winter hats are also a great gift to include with certain "package weekends." For these, consider upgrading to more expensive wholesale caps or scarves so BLACK HAT that your gift is distinctive.

Perhaps you can give solid color hats as regular guest gifts, but present a set that includes cross stitched mittens and wholesale caps to anyone who books a special package at your resort.Choosing The Right Wholesale Hats For Your ResortThere are several different styles of wholesale caps available through wholesale distributors. Take the time to explore your options and choose hats, gloves, mittens or scarves that reflect the style and mood of your winter resort.  Knit earflap hats are especially popular with young adults and teens. These colorful wholesale hats cover the head and ears and feature colorful tassels. If you're looking for a more traditional style, beanies have been around for years, although they used to be called simply "knit caps."

The hat is available in two colors, yellow and beige, which cheers you up and reminds you of the glorious charm of Ipanema. The hat is adorable at every detail, only that it is a little bit hefty: £300.00.Barmah Hats are available all around the world and it's not surprising when you consider what a fantastic hat these are.Barmah offer a range of leather hats using only the finest materials including Australian made leathers, ensures your Barmah Hat will stand the test of time. With a choice of leathers and styles Barmah really have got the bush hat market covered.Barmah Hats developed the original HAT-IN-A-BAG and the Squashy® - the most versatile and durable hat on the market which really does make travelling easier.

The only things left to decide are the hat style and material. The Two Basic Styles Of Baseball Hats. There are two styles to choose from: Structured and Unstructured. Structured caps are BASEBALL HATS great for heavy-duty, daily or several times a week, use. These hats feature structural support inside the hat, which helps them maintain their shape through all the wear and tear a player puts it through. Structured styles have a higher profile than the Unstructured design. This provides a bit more headroom for the player and a slightly larger area on the front of the cap to hold your design. These hats make great high school or college ball caps since they can stand up to rigorous use.Unstructured hats do not have the same kind of support inside the hat.
AfraAusten

Messaggi: 2
Iscritto il: ven 14 set 2018, 7:28

puma shoes

Ronnie Fieg puma shoes looks to begin the new year by revisiting he reworked edition of the classic Puma Disc Blaze. When he initially put his touch on the shoe, he tweaked it a bit, smoothing out the contours along the shoe s toe area. This time he s made the shoe the subject of his Coat of Arms collection.Included are two versions of the shoe, both of which feature midsoles that take on a muddied look. The uppers are built from premium leather and brushed nubuck, all the while utilizing some nice 3M detailing. Meanwhile, his Coat of Arms theme comes into play on the shoes inner soles.Look for them to debut at the new Kith pop up shop opening in Paris, which will coincide with Paris Fashion Week (January 16th through the 22nd from 11am-7pm at 23 Rue De Roi De Sicile). Beginning at 10am on January 15th, Kith will give out tickets for a chance to purchase the shoes. This process will repeat over the duration of the pop-up shop with 84 tickets available per day. If you receive a ticket, you re entitled to purchase the kicks for the retail price of 165 Euros. Stay tuned in for updates.

Top 20 Kicks To Watch For In January Jan 2, 2014 Nike Happy (Nike Air Max) 2014, puma trainers y all, even though Finish Line dropped them early last week Image: Nike via HelmetgameHello and welcome to 2014, where the promise of new kicks on your feet await you and a few million other people that love nothing better than to hang out by their laptop or iPhone on Saturdays at five in the morning (Pacific Time). With the New Year come new expectations, new colorways, new retros (both inspired puma suede and oxymoronic) and apparently (sigh) new prices. So what is the smart sneakerhead going to do in the coming months? They are going to take their time and plot out the key releases that they absolutely positively must have but have the discipline to move on if they miss out. They will make the right connections, not use bots and never overpay for something that will restock in a few weeks or drastically drop in resale value in time.

10 Most Underrated Kicks Of 2013 Dec 28, 2013 Nike So underrated, but the total opposite. Also, the comments on Facebook for this should be hilarious Unless you re one of those crazy people (and by  crazy , I mean freakishly rich and if that s the case, I m willing to be adopted by you) who has to have everything, puma sliders chances are you missed out on more than a few great kicks that dropped this year. Now if you re one those people who live and die by the latest hot release that sells out in a matter of minutes, you really missed out on a lot of great kicks that dropped this year because you re a hypebeast. The reality is that there are going to be kicks that stay on the shelves far longer than others for various reasons and if you re looking for something dope to rock and not break your back either looking for it or paying top dollar for them, this list for the 10 Most Underrated Kicks Of 2013 is for you.

Coming in hot is the new Puma Disc Blaze Lite in a flashy blue color setup.Taking hints from the classic Puma models, The new Disc blaze Lite is sure to be a hit.Covering the shoe is a light to dark blue suede, which is overshadowed by a metallic blue outer. Like some of its competitors, this Puma model contains no laces, and relies on the disc technology. This is achieved by twisting the disc on the shoe to tighten or loosen the shoe when on foot, for comfort and function purposes.Make sure to keep an eye out for these at your local retailers, such as KITH NYCVia EU Kicks.

While it could easily be considered a senior citizen in sneaker years on the low the Puma Suede has been steadily in the mix this year dropping nothing but consistent heat. The scorcher continues with this Puma Suede Animal Pack that we took a look at earlier and are doubling back around for seconds of. This particular set of sneakers comes in purple/black or gold/black and its hard to miss that animal print atop the colorful suede background. If you are interested in this set of Puma s they are available now at select retailers.

In honor of next puma uk year s Chinese New Year, PUMA introduces their Year of the Horse Suede Pack. The pack features both PUMA s Suede and Suede Mid silhouette. The pack features elegant suede uppers beautifully colored in Chocolate Brown and Orange Copper. Paying homage to one of China s greatest past times, a special edition box was created designed to replicate a chess board. The Chinese symbol for horse, has been embroidered into the tongue, and can also been found on the heel and the special edition box. Coming to PUMA and select retailers January 1st, make it your first cop of 2014.
AfraAusten

Messaggi: 2
Iscritto il: ven 14 set 2018, 7:28

Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite