Snow Glass Apples, by Neil Gaiman

I do not know what manner of thing she is. None of us do. She killed her mother in the birthing, but that’s never enough to account for it.

They call me wise, but I am far from wise, for all that I foresaw fragments of it, frozen moments caught in pools of water or in the cold glass of my mirror. If I were wise I would not have tried to change what I saw. If I were wise I would have killed myself before ever I encountered her, before ever I caught him.

Wise, and a witch, or so they said, and I’d seen his face in my dreams and in reflections for all my life: sixteen years of dreaming of him before he reined his horse by the bridge that day, and asked my name. He helped me onto his high horse and we rode together to my little cottage, my face buried in the gold of his hair. He asked for the best of what I had; a king’s right, it was.

His beard was red-bronze in the morning light, and I knew him, not as a king, for I knew nothing of kings then, but as my love. He took all he wanted from me, the right of kings, but he returned to me on the following day, and on the night after that: his beard so red, his hair so gold, his eyes the blue of a summer sky, his skin tanned the gentle brown of ripe wheat.

His daughter was only a child: no more than five years of age when I came to the palace. A portrait of her dead mother hung in the princess’s tower room; a tall woman, hair the colour of dark wood, eyes nut-brown. She was of a different blood to her pale daughter.

The girl would not eat with us.

I do not know where in the palace she ate.

I had my own chambers. My husband the king, he had his own rooms also. When he wanted me he would send for me, and I would go to him, and pleasure him, and take my pleasure with him.

One night, several months after I was brought to the palace, she came to my rooms. She was six. I was embroidering by lamplight, squinting my eyes against the lamp’s smoke and fitful illumination. When I looked up, she was there.


She said nothing. Her eyes were black as coal, black as her hair; her lips were redder than blood. She looked up at me and smiled. Her teeth seemed sharp, even then, in the lamplight.

“What are you doing away from your room?”

“I’m hungry,” she said, like any child.

It was winter, when fresh food is a dream of warmth and sunlight; but I had strings of whole apples, cored and dried, hanging from the beams of my chamber, and I pulled an apple down for her.


Autumn is the time of drying, of preserving, a time of picking apples, of rendering the goose-fat. Winter is the time of hunger, of snow, and of death; and it is the time of the midwinter feast, when we rub the goose-fat into the skin of a whole pig, stuffed with that autumn’s apples; then we roast it or spit it, and we prepare to feast upon the crackling.

She took the dried apple from me and began to chew it with her sharp yellow teeth.

“Is it good?”

She nodded. I had always been scared of the little princess, but at that moment I warmed to her and, with my fingers, gently, I stroked her cheek. She looked at me and smiled—she smiled but rarely— then she sank her teeth into the base of my thumb, the Mound of Venus, and she drew blood.

I began to shriek, from pain and from surprise; but she looked at me and I fell silent.

The little princess fastened her mouth to my hand and licked and sucked and drank. When she was finished, she left my chamber. Beneath my gaze the cut that she had made began to close, to scab, and to heal. The next day it was an old scar: I might have cut my hand with a pocketknife in my childhood.

I had been frozen by her, owned and dominated.

That scared me, more than the blood she had fed on. After that night I locked my chamber door at dusk, barring it with an oaken pole, and I had the smith forge iron bars, which he placed across my windows.

My husband, my love, my king, sent for me less and less, and when I came to him he was dizzy, listless, confused. He could no longer make love as a man makes love; and he would not permit me to pleasure him with my mouth: the one time I tried, he started, violently, and began to weep. I pulled my mouth away and held him tightly, until the sobbing had stopped, and he slept, like a child.

I ran my fingers across his skin as he slept. It was covered in a multitude of ancient scars. But I could recall no scars from the days of our courtship, save one, on his side, where a boar had gored him when he was a youth.

Soon he was a shadow of the man I had met and loved by the bridge. His bones showed, blue and white, beneath his skin. I was with him at the last: his hands were cold as stone, his eyes milky-blue, his hair and beard faded and lusterless and limp. He died unshriven, his skin nipped and pocked from head to toe with tiny, old scars.

He weighed near to nothing. The ground was frozen hard, and we could dig no grave for him, so we made a cairn of rocks and stones above his body, as a memorial only, for there was little enough of him left to protect from the hunger of the beasts and the birds.

So I was queen.

And I was foolish, and young—eighteen summers had come and gone since first I saw daylight—and I did not do what I would do, now.

If it were today, I would have her heart cut out, true. But then I would have her head and arms and legs cut off. I would have them disembowel her. And then I would watch, in the town square, as the hangman heated the fire to white-heat with bellows, watch unblinking as he consigned each part of her to the fire. I would have archers around the square, who would shoot any bird or animal who came close to the flames, any raven or dog or hawk or rat. And I would not close my eyes until the princess was ash, and a gentle wind could scatter her like snow.

I did not do this thing, and we pay for our mistakes.

They say I was fooled; that it was not her heart. That it was the heart of an animal—a stag, perhaps, or a boar. They say that, and they are wrong.

And some say (but it is her lie, not mine) that I was given the heart, and that I ate it. Lies and half-truths fall like snow, covering the things that I remember, the things I saw. A landscape, unrecognizable after a snowfall: that is what she has made of my life.

There were scars on my love, her father’s thighs, and on his ballock-pouch, and on his male member, when he died.

I did not go with them. They took her in the day, while she slept, and was at her weakest. They took her to the heart of the forest, and there they opened her blouse, and they cut out her heart, and they left her dead, in a gully, for the forest to swallow.

The forest is a dark place, the border to many kingdoms; no one would be foolish enough to claim jurisdiction over it. Outlaws live in the forest. Robbers live in the forest, and so do wolves. You can ride through the forest for a dozen days and never see a soul; but there are eyes upon you the entire time.

They brought me her heart. I know it was hers— no sow’s heart or doe’s would have continued to beat and pulse after it had been cut out, as that one did.

I took it to my chamber.

I did not eat it: I hung it from the beams above my bed, placed it on a length of twine that I strung with rowan berries, orange-red as a robin’s breast, and with bulbs of garlic.

Outside, the snow fell, covering the footprints of my huntsmen, covering her tiny body in the forest where it lay.

I had the smith remove the iron bars from my windows, and I would spend some time in my room each afternoon through the short winter days, gazing out over the forest, until darkness fell.

There were, as I have already stated, people in the forest. They would come out, some of them, for the Spring Fair: a greedy, feral, dangerous people; some were stunted—dwarfs and midgets and hunchbacks; others had the huge teeth and vacant gazes of idiots; some had fingers like flippers or crab-claws. They would creep out of the forest each year for the Spring Fair, held when the snows had melted.

As a young lass I had worked at the fair, and they had scared me then, the forest folk. I told fortunes for the fairgoers, scrying in a pool of still water; and, later, when I was older, in a disk of polished glass, its back all silvered—a gift from a merchant whose straying horse I had seen in a pool of ink.

The stall-holders at the fair were afraid of the forest folk; they would nail their wares to the bare boards of their stalls—slabs of gingerbread or leather belts were nailed with great iron nails to the wood. If their wares were not nailed, they said, the forest folk would take them, and run away, chewing on the stolen gingerbread, flailing about them with the belts.

The forest folk had money, though: a coin here, another there, sometimes stained green by time or the earth, the face on the coin unknown to even the oldest of us. Also they had things to trade, and thus the fair continued, serving the outcasts and the dwarfs, serving the robbers (if they were circumspect) who preyed on the rare travelers from lands beyond the forest, or on gypsies, or on the deer. (This was robbery in the eyes of the law. The deer were the queen’s.)

The years passed by slowly, and my people claimed that I ruled them with wisdom. The heart still hung above my bed, pulsing gently in the night. If there were any who mourned the child, I saw no evidence: she was a thing of terror, back then, and they believed themselves well rid of her.

Spring Fair followed Spring Fair: five of them, each sadder, poorer, shoddier than the one before. Fewer of the forest folk came out of the forest to buy. Those who did seemed subdued and listless. The stall-holders stopped nailing their wares to the boards of their stalls. And by the fifth year but a handful of folk came from the forest—a fearful huddle of little hairy men, and no one else.

The Lord of the Fair, and his page, came to me when the fair was done. I had known him slightly, before I was queen.

“I do not come to you as my queen,” he said.

I said nothing. I listened.

“I come to you because you are wise,” he continued. “When you were a child you found a strayed foal by staring into a pool of ink; when you were a maiden you found a lost infant who had wandered far from her mother, by staring into that mirror of yours. You know secrets and you can seek out things hidden. My queen,” he asked, “what is taking the forest folk? Next year there will be no Spring Fair. The travelers from other kingdoms have grown scarce and few, the folk of the forest are almost gone. Another year like the last, and we shall all starve.”

I commanded my maidservant to bring me my looking glass. It was a simple thing, a silver-backed glass disk, which I kept wrapped in a doeskin, in a chest, in my chamber.

They brought it to me, then, and I gazed into it:

She was twelve and she was no longer a little child. Her skin was still pale, her eyes and hair coal-black, her lips blood-red. She wore the clothes she had worn when she left the castle for the last time— the blouse, the skirt—although they were much let-out, much mended. Over them she wore a leather cloak, and instead of boots she had leather bags, tied with thongs, over her tiny feet.

She was standing in the forest, beside a tree.

As I watched, in the eye of my mind, I saw her edge and step and flitter and pad from tree to tree, like an animal: a bat or a wolf. She was following someone.

He was a monk. He wore sackcloth, and his feet were bare, and scabbed and hard. His beard and tonsure were of a length, overgrown, unshaven.

She watched him from behind the trees. Eventually he paused for the night, and began to make a fire, laying twigs down, breaking up a robin’s nest as kindling. He had a tinderbox in his robe, and he knocked the flint against the steel until the sparks caught the tinder and the fire flamed. There had been two eggs in the nest he had found, and these he ate, raw. They cannot have been much of a meal for so big a man.

He sat there in the firelight, and she came out from her hiding place. She crouched down on the other side of the fire, and stared at him. He grinned, as if it were a long time since he had seen another human, and beckoned her over to him.

She stood up and walked around the fire, and waited, an arm’s length away. He pulled in his robe until he found a coin—a tiny, copper penny—and tossed it to her. She caught it, and nodded, and went to him. He pulled at the robe around his waist, and his robe swung open. His body was as hairy as a bear’s. She pushed him back onto the moss. One hand crept, spider-like, through the tangle of hair, until it closed on his manhood; the other hand traced a circle on his left nipple. He closed his eyes, and fumbled one huge hand under her skirt. She lowered her mouth to the nipple she had been teasing, her smooth skin white on the furry brown body of him.

She sank her teeth deep into his breast. His eyes opened, then they closed again, and she drank.

She straddled him, and she fed. As she did so a thin blackish liquid began to dribble from between her legs. . . .

“Do you know what is keeping the travelers from our town? What is happening to the forest people?” asked the Head of the Fair.

I covered the mirror in doeskin, and told him that I would personally take it upon myself to make the forest safe once more.

I had to, although she terrified me. I was the queen.

A foolish woman would have gone then into the forest and tried to capture the creature; but I had been foolish once and had no wish to be so a second time.

I spent time with old books. I spent time with the gypsy women (who passed through our country across the mountains to the south, rather than cross the forest to the north and the west).

I prepared myself, and obtained those things I would need, and when the first snows began to fall, I was ready.

Naked, I was, and alone in the highest tower of the palace, a place open to the sky. The winds chilled my body; goose pimples crept across my arms and thighs and breasts. I carried a silver basin, and a basket in which I had placed a silver knife, a silver pin, some tongs, a grey robe, and three green apples.

I put them down and stood there, unclothed, on the tower, humble before the night sky and the wind. Had any man seen me standing there, I would have had his eyes; but there was no one to spy. Clouds scudded across the sky, hiding and uncovering the waning moon.

I took the silver knife and slashed my left arm— once, twice, three times. The blood dripped into the basin, scarlet seeming black in the moonlight.

I added the powder from the vial that hung around my neck. It was a brown dust, made of dried herbs and the skin of a particular toad, and from certain other things. It thickened the blood, while preventing it from clotting.

I took the three apples, one by one, and pricked their skins gently with my silver pin. Then I placed the apples in the silver bowl, and let them sit there while the first tiny flakes of snow of the year fell slowly onto my skin, and onto the apples, and onto the blood.

When dawn began to brighten the sky I covered myself with the grey cloak, and took the red apples from the silver bowl, one by one, lifting each into my basket with silver tongs, taking care not to touch it. There was nothing left of my blood or of the brown powder in the silver bowl, nothing save a black residue, like a verdigris, on the inside.

I buried the bowl in the earth. Then I cast a glamour on the apples (as once, years before, by a bridge, I had cast a glamour on myself), that they were, beyond any doubt, the most wonderful apples in the world, and the crimson blush of their skins was the warm colour of fresh blood.

I pulled the hood of my cloak low over my face, and I took ribbons and pretty hair ornaments with me, placed them above the apples in the reed basket, and I walked alone into the forest, until I came to her dwelling: a high, sandstone cliff, laced with deep caves going back a way into the rock wall.

There were trees and boulders around the cliff-face, and I walked quietly and gently from tree to tree, without disturbing a twig or a fallen leaf. Eventually I found my place to hide, and I waited, and I watched.

After some hours a clutch of dwarfs crawled out of the hole in the cave-front—ugly, misshapen, hairy little men, the old inhabitants of this country. You saw them seldom now.

They vanished into the wood, and none of them espied me, though one of them stopped to piss against the rock I hid behind.

I waited. No more came out.

I went to the cave entrance and hallooed into it, in a cracked old voice.

The scar on my Mound of Venus throbbed and pulsed as she came toward me, out of the darkness, naked and alone.

She was thirteen years of age, my stepdaughter, and nothing marred the perfect whiteness of her skin save for the livid scar on her left breast, where her heart had been cut from her long since.

The insides of her thighs were stained with wet black filth.

She peered at me, hidden, as I was, in my cloak. She looked at me hungrily. “Ribbons, goodwife,” I croaked. “Pretty ribbons for your hair . . .”

She smiled and beckoned to me. A tug; the scar on my hand was pulling me toward her. I did what I had planned to do, but I did it more readily than I had planned: I dropped my basket, and screeched like the bloodless old peddler woman I was pretending to be, and I ran.

My grey cloak was the colour of the forest, and I was fast; she did not catch me.

I made my way back to the palace.

I did not see it. Let us imagine though, the girl returning, frustrated and hungry, to her cave, and finding my fallen basket on the ground.

What did she do?

I like to think she played first with the ribbons, twined them into her raven hair, looped them around her pale neck or her tiny waist.

And then, curious, she moved the cloth to see what else was in the basket; and she saw the red, red apples.

They smelled like fresh apples, of course; and they also smelled of blood. And she was hungry. I imagine her picking up an apple, pressing it against her cheek, feeling the cold smoothness of it against her skin.

And she opened her mouth and bit deep into it….

By the time I reached my chambers, the heart that hung from the roof-beam, with the apples and hams and the dried sausages, had ceased to beat. It hung there, quietly, without motion or life, and I felt safe once more.

That winter the snows were high and deep, and were late melting. We were all hungry come the spring.

The Spring Fair was slightly improved that year. The forest folk were few, but they were there, and there were travelers from the lands beyond the forest.

I saw the little hairy men of the forest-cave buying and bargaining for pieces of glass, and lumps of crystal and of quartz-rock. They paid for the glass with silver coins—the spoils of my stepdaughter’s depredations, I had no doubt. When it got about what they were buying, townsfolk rushed back to their homes, came back with their lucky crystals, and, in a few cases, with whole sheets of glass.

I thought, briefly, about having the little men killed, but I did not. As long as the heart hung, silent and immobile and cold, from the beam of my chamber, I was safe, and so were the folk of the forest, and, thus, eventually, the folk of the town.

My twenty-fifth year came, and my stepdaughter had eaten the poisoned fruit two winters back, when the prince came to my palace. He was tall, very tall, with cold green eyes and the swarthy skin of those from beyond the mountains.

He rode with a small retinue: large enough to defend him, small enough that another monarch—myself, for instance—would not view him as a potential threat.

I was practical: I thought of the alliance of our lands, thought of the kingdom running from the forests all the way south to the sea; I thought of my golden-haired bearded love, dead these eight years; and, in the night, I went to the prince’s room.

I am no innocent, although my late husband, who was once my king, was truly my first lover, no matter what they say.

At first the prince seemed excited. He bade me remove my shift, and made me stand in front of the opened window, far from the fire, until my skin was chilled stone-cold. Then he asked me to lie upon my back, with my hands folded across my breasts, my eyes wide open—but staring only at the beams above. He told me not to move, and to breathe as little as possible. He implored me to say nothing. He spread my legs apart.

It was then that he entered me.

As he began to thrust inside me, I felt my hips raise, felt myself begin to match him, grind for grind, push for push. I moaned. I could not help myself.

His manhood slid out of me. I reached out and touched it, a tiny, slippery thing.

“Please,” he said, softly. “You must neither move nor speak. Just lie there on the stones, so cold and so fair.”

I tried, but he had lost whatever force it was that had made him virile; and, some short while later, I left the prince’s room, his curses and tears still resounding in my ears.

He left early the next morning, with all his men, and they rode off into the forest.

I imagine his loins, now, as he rode, a knot of frustration at the base of his manhood. I imagine his pale lips pressed so tightly together. Then I imagine his little troupe riding through the forest, finally coming upon the glass-and-crystal cairn of my stepdaughter. So pale. So cold. Naked, beneath the glass, and little more than a girl, and dead.

In my fancy, I can almost feel the sudden hardness of his manhood inside his britches, envision the lust that took him then, the prayers he muttered beneath his breath in thanks for his good fortune. I imagine him negotiating-with the little hairy men—offering them gold and spices for the lovely corpse under the crystal mound.

Did they take his gold willingly? Or did they look up to see his men on their horses, with their sharp swords and their spears, and realize they had no alternative?

I do not know. I was not there; I was not scrying. I can only imagine… .

Hands, pulling off the lumps of glass and quartz from her cold body. Hands, gently caressing her cold cheek, moving her cold arm, rejoicing to find the corpse still fresh and pliable.

Did he take her there, in front of them all? Or did he have her carried to a secluded nook before he mounted her?

I cannot say.

Did he shake the apple from her throat? Or did her eyes slowly open as he pounded into her cold body; did her mouth open, those red lips part, those sharp yellow teeth close on his swarthy neck, as the blood, which is the life, trickled down her throat, washing down and away the lump of apple, my own, my poison?

I imagine; I do not know.

This I do know: I was woken in the night by her heart pulsing and beating once more. Salt blood dripped onto my face from above. I sat up. My hand burned and pounded as if I had hit the base of my thumb with a rock.

There was a hammering on the door. I felt afraid, but I am a queen, and I would not show fear. I opened the door.

First his men walked into my chamber and stood around me, with their sharp swords, and their long spears.

Then he came in; and he spat in my face.

Finally, she walked into my chamber, as she had when I was first a queen, and she was a child of six. She had not changed. Not really.

She pulled down the twine on which her heart was hanging. She pulled off the rowan berries, one by one; pulled off the garlic bulb—now a dried thing, after all these years; then she took up her own, her pumping heart—a small thing, no larger than that of a nanny goat or a she-bear—as it brimmed and pumped its blood into her hand.

Her fingernails must have been as sharp as glass: she opened her breast with them, running them over the purple scar. Her chest gaped, suddenly, open and bloodless. She licked her heart, once, as the blood ran over her hands, and she pushed the heart deep into her breast.

I saw her do it. I saw her close the flesh of her breast once more. I saw the purple scar begin to fade.

Her prince looked briefly concerned, but he put his arm around her nonetheless, and they stood, side by side, and they waited.

And she stayed cold, and the bloom of death remained on her lips, and his lust was not diminished in any way.

They told me they would marry, and the kingdoms would indeed be joined. They told me that I would be with them on their wedding day.

It is starting to get hot in here.

They have told the people bad things about me; a little truth to add savour to the dish, but mixed with many lies.

I was bound and kept in a tiny stone cell beneath the palace, and I remained there through the autumn. Today they fetched me out of the cell; they stripped the rags from me, and washed the filth from me, and then they shaved my head and my loins, and they rubbed my skin with goose-grease.

The snow was falling as they carried me—two men at each hand, two men at each leg—utterly exposed, and spread-eagled and cold, through the midwinter crowds, and brought me to this kiln.

My stepdaughter stood there with her prince. She watched me, in my indignity, but she said nothing.

As they thrust me inside, jeering and chaffing as they did so, I saw one snowflake land upon her white cheek, and remain there without melting.

They closed the kiln door behind me. It is getting hotter in here, and outside they are singing and cheering and banging on the sides of the kiln.

She was not laughing, or jeering, or talking. She did not sneer at me or turn away. She looked at me, though; and for a moment I saw myself reflected in her eyes.

I will not scream. I will not give them that satisfaction. They will have my body, but my soul and my story are my own, and will die with me.

The goose-grease begins to melt and glisten upon my skin. I shall make no sound at all. I shall think no more on this.

I shall think instead of the snowflake on her cheek.

I think of her hair as black as coal, her lips, redder than blood, her skin, snow-white.

Pages I run through

Ok, So I have decided to post this list as my motivation to collect and read more books …

This entry is written a while ago (4am ), The sun had already woke up and still I am wide awake.. @_@

And since I cannot sleep, I decided to  check for logical gaps and edit my proofs for my problem set due this week, and

of course to publish this.

Here is the list of books I’ve read, and still reading..

This is quite an accomplishment for me, because I am the type of person who likes to start reading then,

give up when I’m bored or too busy to spare my time reading non-academic stuff.

With no particular order, here  ‘tis.

1. Night- one of the books that reminds me how blessed and comfortable my life is.

2. The curious Incident of the dog in the Night time – one of my favorites, it teaches me  to love Math and Physics. It awakens the “hungry for knowledge” side of me.

3. Love in the Time of Cholera- True love waits. It gave me another perspective of what love really is.

4. ABNKKBSNPLAK- A mirror on my childhood/elementary experiences

5. Alamat ng Gubat- simplistic yet unfathomable.

4. MacArthur- I can’t remember the tone of Bob Ong in this book, but surely he made me laugh

5. Libro ni Hudas-

6. Just like Jesus- Made me cry when I first read this, life changer

7. Purpose Driven Life- another life changer book, a must read

8. What Mad man pursuit- The story of Francis Crick as they unravel the DNA form

9. On the origin of Species- The beagle expedition, and memoir of Mr. Darwin himself. It depicts his struggle as he oppose the church for the development of his research

10. Captivating- I gained a lot of self worth, when I read this book.

11. Lord of the Rings: Fellowship of the Ring- An epic fantasy!!! I fell in love with Tolkien.

12. The Hobbit- Fascinating, well told, and now I wanted a bed sheet with Middle Earth’s map. Yay

13. Angela’s Ashes: It is a depiction of how man struggles to live. McCourt is one of  the best.

14. Eat Pray Love- Yay.. I fell in love with Italy.

15. Uncle Petros and the Goldbach’s Conjecture: “Mathematicians are not made, they are born”, Though I am not born to be it, I am encouraged to add something to the body of knowledge of mankind, by doing my greatest efforts on my productive years.

In Queue (I am reading this in Parallel)

1. My incredibly miserable life

2. The Silmarillion

3. Metamath

4. Harry Potter (Book 1)

Chapter 4: Decidability

After knowing the capabilities of each model of computation, it is outright to know their limitations.

At this point, Turing Machine(TM) is the most powerful model of computation .But one needs to ponder the question “Are there problems that cannot be computed by a TM?”.

This chapter from “Introduction of Theory of Computation” by Michael Sipser, discusses the solvability or decidability of a certain problem


From Chapter 3: Church – Turing Thesis, we learned about languages that are Turing Recognizable and Turing decidable.

From that chapter also, we learned that Every decidable language is Turing recognizable but not all Turing recognizable are decidable.

In this chapter we present languages that are decidable by algorithms.

We will begin with computational problems concerning finite automaton.

  1. ACCEPTANCE PROBLEM: A test whether an automation M accepts a string w.
  2. A test whether the language of finite automaton M is empty or L(M)= null.
  3. A test whether two finite automata M1 and  M2 are equivalent. (When we say equivalent, they should accept the same language)


Given a finite automaton M and a string w, determine whether w ε L(M).

This problem can be expressed in a language, say ADFA

ADFA= {<M,w>| M is a DFA accepting string w}

The original question is similar to determining whether <M,w > is a member of ADFA.

Showing that the Language is decidable is like showing that the problem is decidable.


ADFA is a decidable language.

ADFA= {<M,w>| where M is a DFA accepting w}


Proof Idea:

We simply need to present a TM that decides  ADFA.

TM1= on input <M, w>, where M is a DFA and w is a string

  1. Simulate M on w. (This assumes that M has an encoding for TM)
  2. If the simulation ends on an accept state then TM accepts <M,w>. If is ends on a non accepting state then TM rejects <M,w>


ANFA is a decidable language.

ANFA= {<N,w>| where N is  NFA accepting w}


Proof Idea:

We need to present a TM that decides ANFA, but instead of making  another TM  that decides on ANFA we will make use of TM1 as a subroutine of TM2

TM2= on input <N, w>, where N is an NFA and w is a string

  1. TM2 first converts N to a DFA N’
  1. Simulate DFA N’ to TM1
  2. If TM1 accepts w, accept, if not then reject.


AREX is a decidable language.

AREX= {<R,w>| where R is a regular expression that generates w}


Proof idea:

We need to present TM that decides on AREX.

TM 3 uses TM2 as a subroutine.

TM3= on input <R,w>, where R is a regular expression and w is a string.

  1. Convert the regular expression  R to an equivalent NFA RN.
  2. Simulate RN on TM2.
  3. If TM2 accepts, accept; if TM2 rejects, reject.


EDFA is a decidable language.

EDFA= {<A>| where A is a DFA and L(A)= null}


Proof Idea:

Need to present TM that decides on EDFA.

We know  that a DFA accepts a string if there is a path from the start state to an accept state.

To determine whether L(A)= null or not, we will use a marking algorithm.

T= on input <A> ,where <A> is an encoding of a DFA A

  1. Mark the start state of A
  2. Repeat until no new states are marked
    1. Mark any state connected to a marked state
  3. If no accept state is marked, then accept; otherwise reject.


EQDFA is a decidable language.

EQDFA= {<A,B>| where A  and B are DFAs and L(A)=L(B)}


Proof Idea:

One way to prove the above statement is to show that L(A)is a subset of L(B) and L(B) is a subset of A. That is to show that there is a Turing Machine that decides on L(A) is a subset of L(B) and its reverse.

One elegant algorithm  uses TM T as a subroutine.

First generate a DFA C from A and B.

C = {L©(C) |  L(C) =( L(A) and !L(B) ) or (!L(A) and L(B)) }

L(C) is simply the set difference of L(A) and L(B), so if L(C)=null then

L(A)= L(B)

We will just need to simulate C on TM T.

If its accepts, accept; otherwise, reject.


Now we will consider computational problems concerning CFGs.

Let’s start off with the Acceptance Problem of CFGs


ACFG  is a decidable language.

ACFG= {<C,w>| where C is a CFG and it generates string w}


Proof Idea:

One idea is to generate all derivations of C then check whether w is one of its derivation, This is not a good idea because the TM that will simulate the generation will not stop if w is not derived from C.

This leads us to a Turing Machine that recognizes but not decides on ACFG.

But to make a Turing Machine that will decide on ACFG, we need to have a finite derivations of C. We know that C in its Chomsky Normal Form (CNF) has 2n-1  derivations of w, where n is the length of w. In that case checking only 2n-1 derivations on w is sufficient to determine whether C generates w or not.

Let TM_CFG be the Turing Machine that decides on ACFG

TM_CFG= on input <C,w>, where C is a CFG and w is a string

  1. Convert C to its equivalent CNF denoted by C_CNF.
  2. Generate all 2n-1 derivations of C_CNF.
  3. If w is one of its derivation, accept; otherwise, reject.


ECFG is a decidable language.

ECFG= {<A>| where A is a CFG and L(A)= null}


Proof Idea:

In order to determine whether a grammar can generate a string, we need to test if the start symbols can generate a string of terminals.


TM_ECFG= on input <A>, where A is a CFG

  1. Mark all terminal symbols
  2. Repeat until no new symbol is marked
    1. Mark any variable B if B has a rule, B-> U1,U2,…,Uk and each symbol Ui has already been Marked
  3. If the start state is not marked, accept; otherwise, reject.

EQCFG= {<A,B>| where A and B are CFGs and L(A)= L(B)}

Since the class of CFGs are not closed under complementation or intersection, the proof idea we used in proving EQDFA is not valid. In fact

EQCFG is not decidable!


Every Context free Language is decidable.


Proof Idea:

One (bad) idea one must instantly think is to convert a PDA to a TM, but instead of making use of the infinite tape, the tape should behave as a Stack and since PDA are nondeterministic, we can easily convert a dTM to a nTM.

This idea is not a valid proof for the decidability of every CFG, to be able to decide, TM should halt on all input, and because the generation of strings can possibly end up in an infinite derivation, clearly TM will not decide on the CFG.

Instead we use the Turing Machine that decides on ACFG.


Let A be a CFL. Let G be a CFG for A.

Let TM_CFL be a TM that decides on A.

TM_CFL= on input w

  1. Simulate G on TM_CFL on input w
  1. If this machine accepts w, accept; otherwise, reject.


One of the famous problems that gave birth to the theory of computation is the Halting Problem.

This was proposed by Alan Turing as a hypothetical problem to prove unsolvability.

Though computers  seems to be so powerful, they are still bounded by some limitations.

One can possibly think that  problems that are unsolvable are too complex, but as a surprise, there are set of problems that are deceivingly simple to be classified as unsolvable


ATM= {<M,w>| M is a TM and it accepts w}

Is ATM  decidable??


From Chapter 3 we know that all Turing decidable are Turing Recognizable, but not all Turing Recognizable are decidable. The condition in decidable language(TM should halt on all input) added more restriction to Turing Recognizable.

In this discussion of the Halting problem, we will learn that a n ATM is not decidable. This is proven using a simple proof by contradiction and a method called Diagonalization introduced by Georg Cantor in 1873.

Proof 1: Proof by Contradiction

Let’s assume we have a TM H that decides on ATM.

On input <M, w> where M is a Turing Machine and w is an input string.

H(<M,w>)={accept                          if M accepts w}

{reject                           if M rejects w }

Now we have a Turing Machine D with H as a subroutine.

TM D= on input <M>, where M is a TM

  1. Simulate H on input<<M>, M>
  2. Output the opposite of what H outputs

D(<M>)= {accept if M does not accept

reject if M rejects w }

Now if we run <D> on D

D(<D>)= {accept if  D does not accept

reject if D rejects}

Tadaaa!!! Contradiction, There a Decider H does not exist.

Another method is called the Diagonalization. You can check page 183 of Sipser’s “Introduction to Theory of Computation”.


Some Languages are not Turing-recognizable


Proof Idea:

We just need to show that the number of encoding of problems are infinite while the Turing Machine is finite.

Therefore, there will be problems that cannot be solved by a Turing Machine

The Languages that are not Turing-recognizable belongs to the class of Turing-unrecognizable


A language is decidable iff it is Turing-recognizable and co-Turing recognizable.

Or in other words a language is decidable exactly when both it and its complement are Turing-recognizable.


from this above theorem it follows that !ATM is Turing-unrecognizable.