“Full recall of dreams is impossible because the mortality problem for Turing machines in undecidable.” One of my friends uttered this cryptic phrase during our long conversation about altered states of consciousness – we considered whether one can implant false memories into a victim’s mind by inducing psychotic dreams (using a mix of trance music, drugs and rapidly moving kaleidoscopic images) and then making the victim confuse the dreams with their memories. The conversation quickly moved to something else (Sumerian religion or relative attractiveness of redheads vs albinos – can’t remember) and I forgot to ask for explanations. Here is my attempt at reconstructing the argument.

A Turing Machine M is called mortal if it halts when run any starting configuration. In particular, the tape content and initial state can be arbitrary. A mortal machine is “impossible to break” – it will halt even if run on a “faulty”, random internal configuration. This is precisely the state we experience whilst in a dream. Our mind is thrown in the middle of a jumbled “world configuration”, with no past, no rhyme or reason. The mortality problem – deciding whether a given Turing machine M is mortal or not – is undecidable (note that the proof is much more involved then the undecidability of the halting problem). Now, come to think of it, my friend tried to infer something in the wrong direction: if “undecidability => impossibility of dream recall”, then “possibility of dream recall => decidability”. But I don’t see how recalling one’s dreams could help in solving the mortality problem. Possibly he meant that “decidability => possiblity of dream recall”, because if we assume that the brain is a Turing machine and could inspect its own state, then blah blah etc. Seems like totally faulty logic to me. But still…

Take an ordinary Turing machine, maybe performing simple arithmetic operations (add two numbers in binary). What will happen if we run it on a NONRECURSIVE input tape configuration? Will it slowly go mad and compute forever, or forget its purpose and become numb? Or will it somehow find a way out to normality (but how?) and halt? I once had a dream where I was in unfamiliar surroundings (something like a hidden part of Warsaw, only much bigger and “deeper”, in a metaphysical sense). It felt like a middle of some convoluted story whose context I didn’t know. And then I felt, for a split second, THE SCENT OF EVENING. Springtime, smell of rain. First true love. Sunsets and cinnamon. I wondered if I would “halt”, too, or this dream could continue forever…