[SP-pm] perl regexes & turing machines

[Nuba Princigalli]

Caros,

On Mon, 19 Jul 2010, Eden Cardim wrote:
> E acho que regexes perl são turing-complete mesmo sem apelar para perl
> inline, já que tem match condicional: (?(condition)yes-pattern|no-pattern) e
> buffers de captura.

Eu estava na duvida também, e garimpei isso aqui hoje cedo no perlmonks:
http://www.perlmonks.org/?node_id=406253

Pra mim o que o blockhead postou responde muito bem. So nao vou falar o
veredicto aqui pra fazer a galera ler esses dois snipptes pelo menos rsrs:

"A Turing machine must have unbounded memory. A Perl regex using only captures
& backreferences has a bounded (linear in the size of input) amount of "memory"
about the its input -- the number of captures is fixed when the regular
expression is compiled, and each capture contains at most the entire string.
Not only that, but the type of access to this memory is very stricly limited:
you can only match substrings. In addition, you don't have write access to this
memory in any sort of arbitrary fashion (apart from trying a different
substring of the input -- which is hardly arbitrary, and could be viewed as
just a form of nondeterminism). This is an essential feature for the power of a
Turing machine."

e

"Footnote: when a system has a finite number (say, N) of possible
configurations on a given input, you can answer the halting problem for it as
follows (where "halting" means entering some special subset of configurations):
Simulate it for N steps. If it hasn't reached a halting configuration by then,
it must repeat a configuration. Since the next configuration depends only on
the previous configuration, it must be in an infinite loop and thus will never
reach a halting configuration. Turing machines have an infinite tape and thus
an infinite number of possible configurations.

Clearly if you can answer halting queries on a system, it is not universal
(Halting Problem)."

Abraco,

Nuba