# Post to walk to the Edge

## Decide if it were or not possible, or even intractable

It’s not true that we can calculate anything we propose with a computer. This is something that was discovered 100 years ago. No matter what notation is chosen, there are problems where you can’t be sure that a machine can conclude with an answer.

The problems that cannot be associated with any kind of algorithm that solves them are the **undecidable **ones. Perhaps that is **Post**’s most interesting legacy: the problem of correspondence. The undecidable problem possibly easier to formulate and, perhaps because of that, to work with.

That means that if you had a sequence of *K* naturals with two encoding *α** *and ** β**, and if you had two functions defined

*g*and

*f*from the same sequence which constitute a

**word**

*g*with

**and**

*α**f*with

**,**

*β*you couldn’t ensure there were a *sequence *where *g(sequence)* = *f(sequence)*.

Imagine *g* is Spanish and *h* is English, *α** *and ** β **could be their dictionaries from the same

*mentality*to understand an

*idea*, so there is no way to know if two languages can construct the same

*idea*. Considering this concept, we can construct a diccionary

*α**/*

**to get all the correspondences for every roleplay, like:**

*β*

*α**/*

**= a/baa, ab/aa, bba/bb.**

*β*For K = 4, if we take as solution 3, 2, 3, 1 = bba·ab·bba·a = bb·aa·bb·baa

As you can see that is the same string, but in different association.

# Entering to the code

We could code anything to solve that undecidable problem in this way,

def explodePost(dicc): Q = set([]) newQ = clausure(('', ''), dicc) while newQ: query = newQ.pop() if query in Q: continue newQ.update(clausure(query, dicc)) if ('', '') in newQ: return True Q.add(query) return Falsedef clausure(query, dicc): R = set([]) q1, q2 = query for x1 in dicc.keys(): qR = rest(q1+x1, q2+dicc[x1]) if qR is not None: R.add(qR) return Rdef rest(str1, str2, CAB = "$_$"): if CAB + str1 in CAB + str2: return ('', str2[len(str1):]) if CAB + str2 in CAB + str1: return (str1[len(str2):], '') return None

Now you can think, if there is no code possible, how do you construct a code? Obviously, the problem is that we cannot ensure this code will finish. But you can test some things:

```
>>> rest('my cat', 'my dog')
>>> rest('my ', 'my dog')
('', 'dog')
>>> clausure(('', ''), {'a':'baa', 'ab':'aa', 'bba':'bb'})
{('a', '')}
>>> explodePost({'a':'baa', 'ab':'aa', 'bba':'bb'})
True
>>> explodePost({'a':'baa', 'ab':'aa', 'baa':'bb'})
False
```

So, almost for some entries we can ensure if Post Correspondence is True os False.

## Why it could not work

Imagine we construct strings like *x[Q]y#*, where *x* and* y* are strings in an alphabet and *Q* represent one possible state register in a Turing Machine placed in the middle of a tape (position could be *len(x)* in the pattern *x[Q]y#*).

So, every correspondence in *α** /* ** β **is able to represent any behavioural change in our

**Turing Machine**simulation. For example,

- if we read in the state Q1 the letter ‘a’ then move to the right, put a ‘b’ and change to Q2 → [Q1]a / b[Q2]
- with {‘a’, ‘b’} alphabet, from Q1 move to the left and change to Q2 → a[Q1]a/[Q2]aa, a[Q1]b/[Q2]ab, b[Q1]a/[Q2]ba, b[Q1]b/[Q2]bb

That means that if we were able to solve the **Post’s correspondence** (like the *explodePost *code) then we would be able to guess if a Turing Machine is able to accept a specific entry, and that is not possible considering that constructing a code able to guess when every code halts could be the next step.

# What I ensure about NP Vs P

Imagine you are working with a sequence of *K* elements. That sequence is the index we will use to ensure us if it constructs the same result *f*(seq) = *g*(seq).

def testPost(seq, items): A = '' B = '' for i in seq: A += items[i][0] B += items[i][1] return A == B>>> testPost((2, 1, 2, 0), [('a', 'baa'), ('ab', 'aa'), ('bba', 'bb')]) True

In linear time we can test if entry of pairs has a correspondence if we put previously a sequence. So, if we establish a maximum *K*, length of every sequence, this problem will be easy to verificate. That means that exists a **Turing Machine** bounded linearly which will accept that entry, and we can configure that machine with *K* undetermined values, in a non-deterministic way.

When we can accept an entry in polynomial time under a finite number of **Turing Machines**, we consider that problem **NP**. If code which accepts the entry works in polynomial time, the problem will be in **P**.

- Easy verification
*AND*Solvable problem =**NP**problem - Easy solution =
**P**problem

In fact, we always could establish a maximum *K* independently of the input. So in the code above, *testPost*, there were a maximum number of *seq*; where *seq *is the certificate needed by the **Non — deterministic Turing Machine** defined in *items *to accept the entry. There is no relation between *K* and the code needed to accept the input (no code need to decode *K* anyway). So we necessarily infer that **P **is different from **NP**.

## Moreover

Imagine we construct a string **w **in an alphabet. We decide to divide the string into *K* substrings in two different ways. So now we have *K* pairs of substrings as *validEntry *which work as an entry of **Post’s Correspondence**. Knowing that `explodePost(validEntry)`

will return *True *in a finite time (*explodePost(validEntry)* is a Solvable Problem), but if we do not know which value is *K*, the code cannot be easy solvable.

Suppose we though knowing *K* we will get an easy solvable code,

- code(
*K*;*validEntry*) returns the valid sequence in Polynomial time. - code(
*K*;*anyEntry*) returns a result in Polynomial time.

If *anyEntry *is valid, it will return the valid sequence, and you can test if is a valid entry. If it is not valid, it will return anything, but considering a not valid string you will notice that, so you can generate a test where:

- testPost(code(K; anyEntry), anyEntry) returns
**Post’s correspondence**in polynomial time.

That means that we only need to create a code from a parameter K, and this code will accept anyEntry to generate the sequence. But that is absurd: how can we configure all the codes for every length of the sequences if we are not able to construct a general code for every one?

So I see there are problems in the class **NP **out of the class **P**.

# Conclusions

As we can see, many problems considered very complicated can be simplified thanks to this notation. If you wanted to make sure when an entry has no solutions, you could also invent some tricks.

For example: for the entry {a/baa, ab/aa, bba/bb} you can transform it in {$a$/$baa$, $ab$/$aa$, $bba$/$bb$}. So every pair can be embedded in a vector by a 2-gram where $a$/$baa$ could be {‘$a’:1, ‘$b’:-1, ‘ba’: -1, ‘aa’:-1}. After that, you construct your matrix with as many rows as the size of the entry. Can we find a solution with that matrix like a homogeneous system of equations? If the response is not, then the entry has no solution.

As you can see, even having a way to process the Post’s Correspondency Problem,

- If the System of Homogeneus Equations fails, there will be no solution for the Post one.
- If the Post’s Bounded by K generates a solution, the Post one shares that solution.

Even when you can take everything for ended, there is always a code that can help you walking on.