This kind of problem is mentioned in a book I have read, but the book did not give a concrete example.

If any such problem existed, this might help me understand human creativity. I think it would also prove that we are more than just a Turing machine.

  • You could find a problem which has been solved by creativity rather than through a formal system, but I cannot see how a problem could exist that can not be solved through a formal system, and proven to be such. Even if you take non-polynomial type problems, they are solvable within a formal system (just in exponential time), and humans certainly haven't solved them any other way. You may wish to clarify if you really mean problems which 'cannot' be solved formally, or just ones which 'have not' been solved that way. The two would be very different questions.
    – user22791
    Commented Jan 10, 2017 at 7:42
  • answering the question "why?" when it is not satisfied with an explanation addressing "how?"
    – MmmHmm
    Commented Jan 10, 2017 at 8:06
  • Actually, there is no device that is equivalent to a real Turing machine. Turing machines are conceived to have infinite tapes, i.e. infinite memory capacity. But our physical computers have finite memory and so are merely "instantiations" of an abstraction called "deterministic finite automaton".
    – viuser
    Commented Jan 10, 2017 at 18:59
  • 1
    The book is likely referring to the controversial Lucas-Penrose argument against mechanism:"Since the Gödel sentence cannot be proven in the system, the machine will be unable to produce this sentence as a truth of arithmetic. However, a human can look and see that the Gödel sentence is true. In other words, there is at least one thing that a human mind can do that no machine can". It was pointed out that properly programmed machine can also construct Gödel sentences and "see" that they are "true".
    – Conifold
    Commented Jan 10, 2017 at 19:23
  • 2
    I suspect you need to reformulated the question as something like "problems that can be expresses but not solved in a formal system." Lots of (most? all) practical problems can only be solved by human ingenuity. Ex. keeping our shoes attached to our feet.
    – user20153
    Commented Jan 10, 2017 at 20:50

3 Answers 3


There is no agreed upon example of this kind.

Let us explore the issues:

First, we cannot even come up with a decent example of a problem not solvable by any formal system. If you state the problem you want to use, I can simply put solving that problem as a basic entity in a formal system, and thus find a formal system to solve it. If you disagree that this defines a formal system, I am going to return the challenge and claim that your problem was not well-defined in the first place.

So, we need to fix the formal system we want to talk about. The question already mentions Turing machines, so let's go for that. There clearly are problems not solvable by a Turing machine, so we can ask whether there are any problems not solvable by a Turing machine, but by a human.

A typical candidate could be something like "writing poetry". Now, I can of course take my favourite poem, and code it into a Turing machine that prints it. Does this Turing machine write poetry?

One might say no, because the poem is hard-coded into the machine. However, looking at Kolmogorov complexity and the results in that area, it becomes clear that "hard-coded into the machine" is not really a well-behaved notion. In particular, I could obfuscate the code so much that finding out that the TM writes that poem essentially requires running it.

If the objection is that someone else has written the poem before, and the TM merely replicates it: With access to a thesaurus, some basic verse rules and a few complex calculations I could create a TM that writes something that looks like a poem, without me or anyone else having had an explicit mental representation of the poem before reading the output. Short of a Chinese Room argument, it becomes difficult to reject this.

So far we have discussed only a single poem. Will creativity show in the long run? So we could ask for a steady stream of "substantially different" poems. Depending on what substantially different means, it might still be easy enough to code a TM for that. On the other hand, it is no longer obvious that a human can do that. Maybe any human has only the capacity [hardcoded? :)] for a certain number of poems. Any proof you could give me that you really can keep writing poetry (issues of mortality aside), I could turn into a TM that keeps writing poetry.

As poetry is just a stand-in for an arbitrary candidate, the arguments above should show that there is no easy way to get people to agree that a certain problem matches your criteria. Moreover, as neither the claim nor its converse are falsifiable, there is no obvious default position on this either.

  • 2
    – user6917
    Commented Jan 11, 2017 at 20:41
  • 1
    Nice link! Based on my own abbysmal guessing rate, and noting that the general public does not seem to fare that well either, I would consider that emperical evidence that programs can indeed write poetry (or alternatively, that humans can't either).
    – Arno
    Commented Jan 11, 2017 at 20:49
  • mine was better on the random one than the quiz. yiou gotta learn the knack, i think, as you would with any poet, or art. haha
    – user6917
    Commented Jan 11, 2017 at 21:08
  • Well I've seen meaningful poems and meaningless poems. Of course, one does not expect a meaningless poem to be very different from a bot-generated poem. Remember that there was a paint-bucket-splash that was sold as art. You don't even need a robot to do that!
    – user21820
    Commented Mar 17, 2017 at 9:00

Every formal system was once the creative construction of an individual or a group of individuals to solve a problem that an existing formal system had not already solved.

The best example I can give is communication. Including both verbal and written, we now have hundreds, if not thousands, of formal communication systems because groups creatively solved the problem of "how do I communicate with another?".

Inventions, including the Turning Machine, were also initially creative until they become integral aspects of a formal system. Consider transportation. Hundreds of examples exist on the different and often very creative or impractical solutions for "how do I get from here to there?".

The formal system is itself a creative solution for "how can I assure others can recreate my creation themselves?". This leads us to "writing poetry". There are formal poetry standards but the first haiku was a creative solution to express someone's thoughts or feelings that got formalized so that others could write a similar poem.

  • As we know,some problems can't be solved in an exist formal system.what you said is we could work it out and set up a new system? If so,what about AI?Will it have this gift and how to realize it?How about deep learning?
    – Lufamily
    Commented Jan 12, 2017 at 15:25
  • Artificial Intelligence will be setup like Biological Intelligence has, primarily through trial and error of building upon existing systems into new and more complex systems. And really that's more a question regarding emergence than anything because perhaps there is no solution. Nature can make intelligence sure, but there may not be any way for people to replicate it. I don't think that's true, if it already exists in one form, ours, then we should be able to recreate it, AI and once we do it seems to me that it will be by a creative system of existing and to be discovered systems. Commented Jan 12, 2017 at 21:40

Formal systems are creative constructs of humans. They didn't boot themselves into existence.

The main problem they can't solve is understanding simply because we have no theory of consciousness that works. Turing got around this problem by simply saying imitativeness is enough, and so it has proven to be for most practical purposes.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .