Configurações
controlecabeça
fita de leitura e escrita
1 0 1 1 0 1 1 1
q7
⊔⊔⊔
Configuração 1 0 1 q7 1 0 1 1 1
Complexidade Computacional – p. 137
Linguagem de uma MT
Uma máquina de Turing aceita a entrada w se existe umasequência de configurações C1, C2, . . . , Ck tal que
1. C1 é a configuração inicial de M com entrada w,
2. cada Ci leva a Ci+1 para i = 1, . . . , k − 1, e
3. Ck é uma configuração de aceitação.
A linguagem de M , ou a linguagem reconhecida por M ,denotada por L(M), é o conjunto de cadeias que ela aceita.
Complexidade Computacional – p. 138
Liguagens reconhecíveis
Uma linguagem é Turing-reconhecível se existe algumamáquina de Turing que a reconhece (linguagemrecursivamente enumerável).
Exemplos:As linguagens a seguir são Turing-reconhecíveis:
L(M0) = {u 0 0 : u ∈ {0, 1}∗}L(M2) = {02
n
: n ≥ 0}
Observação: se w não está em L(M) então M pode nãoparar com w como entrada.
Complexidade Computacional – p. 139
Liguagens reconhecíveis e decidíveisUma máquina de Turing M é decisora se sempre aceita ourejeita sua entrada. Dizemos que M decide L(M).
Uma linguagem é Turing-decidível ou simplesmentedecidível se existe alguma máquina de Turing que adecide (linguagem recursiva).
Exemplos:As linguagens a seguir são Turing-decidíveis:
L(M0) = {u 0 0 : u ∈ {0, 1}∗}L(M2) = {02
n
: n ≥ 0}
Toda linguagem decidível é Turing-reconhecível.
Complexidade Computacional – p. 140
Variante simples
δ : (Q \ {qaceitação, qrejeição}) × Γ → Q × Γ × {L,R, P},
onde P representa que a cabeça deve ficar parada.
Complexidade Computacional – p. 143
Variante simples
δ : (Q \ {qaceitação, qrejeição}) × Γ → Q × Γ × {L,R, P},
onde P representa que a cabeça deve ficar parada.
Uma MT com essa possibilidade pode ser simulada poruma MT comum trocando cada transição que não se movepor duas transições: uma para a direita e outra para aesquerda.
Complexidade Computacional – p. 143
Máquinas de Turing multifita
controlecabeça
fitas de leitura e escrita
aaa
a
b
b b
c
⊔
⊔⊔ ⊔⊔⊔⊔
⊔ ⊔ ⊔ ⊔⊔⊔⊔
⊔⊔0 0000 1111
Complexidade Computacional – p. 144
Sobre os componentesComponentes de uma máquina de Turing multifica:
Controle : possui um conjunto finito de estados, dentreseles há 3 estados especiais: inicial, aceitação erejeição. Inicialmente está no estado inicial.
Cabeças : Uma cabeça para cada fita. Cada cabeça lê osímbolo na posição sobre a qual está, escreve umsímbolo nessa posição e move uma posição para adireita ou esquerda. Inicialmente cada cabeça estásobre a primeira posição de sua fita;
Fitas: infinitas à direita. Inicialmente a primeira fitacontém a cadeia representando a entrada do problemanas primeiras posições, as demais posições contém⊔s. As demais fitas contém apenas ⊔s.
Complexidade Computacional – p. 145
Máquinas de Turing multifita
Uma máquina de Turing multifita é como uma MT comumcom várias fitas.
Cada fita tem sua própria cabeça para leitura e escrita.
Inicialmente a entrada aparece na fita 1 e as outras fitasestão em branco.
Função de transição para máquina com k fitas:
δ : (Q \ {qaceitação, qrejeição}) × Γk → Q × Γk × {L,R, P}k.
Complexidade Computacional – p. 146
Máquinas de Turing multifitaA expressão
δ(qi, a1, . . . , ak) = (qj , b1, . . . , bk, L,R, . . . , L)
significa que se a máquina está no estado qi e as cabeçasestão lendo os símbolos
a1, a2, . . . , ak,
respectivamente nas fitas de 1 a k, ela vai para o estado qj
e escreveb1, b2, . . . , bk,
nas k-fitas, movendo a primeira cabeça para a esquerda, asegunda para a direita, . . ., e a última para a esquerda.
Complexidade Computacional – p. 147
Exemplo de MT multifita
Descrição alto nível de uma máquina de Turing que decidese uma dada cadeia w está na linguagem
{z : z ∈ {0, 1}∗, z = zR}.
M1 = “Com entrada w:
▽0 1 1 0 0 0 0 0 0 1 1 0 ⊔ ⊔ . . .
Complexidade Computacional – p. 148
Exemplo de MT multificaDescrição alto nível de uma máquina M5 com duas fitasque decide
M5 = “Com entrada w:
1. copie entrada para 2a¯ fita.
2. mova a cabeça da 1a¯ fita para a primeira posição,
mova a cabeça da 2a¯ fita para a última posição
3. Mova simultaneamente a cabeça da 1a¯ fita para a
direita e da 2a¯ fita para a esquerda. Se em algum
passo os símbolos sobre as cabeças forem diferentes,então rejeite, senão aceite.
Complexidade Computacional – p. 149
Diagrama de estados paraM 5
q0 q1 q2 q3
qa
0,⊔ → 0, 0, R,R
1,⊔ → 1, 1, R,R
0,⊔ → 0, 0, R,R
1,⊔ → 1, 1, R,R
⊔,⊔ → L,L
0, ? → L, P
1, ? → L, P
0, 0 → R,L
1, 1 → R,L
0, 0 → R,L
1, 1 → R,L
⊔, ? → P , P⊔,⊔ → P , P
Transições ausentes levam para qrejeição
Complexidade Computacional – p. 150
Número de passos
Se a cadeia de entrada tem comprimento n então amáquina M5 faz não mais do que 3n passos.
Complexidade Computacional – p. 151
MT multifita por MT fita únicaDuas máquinas são equivalentes se elas reconhecem amesma linguagem.
Teorema . Dada uma máquina de Turing multifitaM , podemos construir uma uma máquina de Turing
S com uma única fita e equivalente a M .
Prova: Vamos mostrar como converter M para S.Digamos que M tenha k fitas.
Complexidade Computacional – p. 152
Ilustração da idéia da prova
M
S
a
aaa
aaa
•a
b b
bb
b
•b
⊔⊔ ⊔ ⊔ ⊔⊔⊔⊔
⊔⊔⊔
⊔ ⊔⊔ ⊔⊔⊔⊔
⊔ ⊔⊔
0000
0 000 1
•1# ###
Complexidade Computacional – p. 153
S = “Com entrada w = w1w2 · · ·wn:
1. Acerte a fita de S para representar todas as k fitas deM :
#•
w1 w2 · · ·wn#•
⊔ #•
⊔ # · · ·#2. Para simular um movimento de M , S percorre sua fita
do primeiro #, que marca o início da fita, até ok + 1-ésimo #, que marca o fim da fita, para determinaros símbolos sob as cabeças. Então S faz uma segundapassada para atualizar as fitas, de acordo com odeterminado pela transição de M .S precisa ter novos estados correspondentes aospossíveis estados de M e aos possíveis conteúdos dasfitas:
Q × Γk
Complexidade Computacional – p. 154
3. Se em algum ponto S move uma das cabeças à direitapara um #, S precisa escrever um branco, deslocandoantes o # e o restante da fita uma posição à direita.”
Complexidade Computacional – p. 155
Corolário . Uma linguagem é Turing-reconhecívelse e somente se alguma máquina de Turing
multifita a reconhece.
Prova:
(⇒) Uma máquina de Turing comum é um caso particularde uma máquina de Turing multifita.
(⇐) Segue do teorema anterior.
Complexidade Computacional – p. 156
Funções den
5n2 − 9n 4n + 8 ⌊n/3⌋ + 4 2√
n + 7
2n−3 lg n (= log2 n)
Qual é maior: n2 − 9 ou 4n + 8?
Complexidade Computacional – p. 158
Funções den
5n2 − 9n 4n + 8 ⌊n/3⌋ + 4 2√
n + 7
2n−3 lg n (= log2 n)
Qual é maior: n2 − 9 ou 4n + 8?
Depende do valor de n!
Complexidade Computacional – p. 158
Funções den
5n2 − 9n 4n + 8 ⌊n/3⌋ + 4 2√
n + 7
2n−3 lg n (= log2 n)
Qual é maior: n2 − 9 ou 4n + 8?
Depende do valor de n!
Qual cresce mais?
Complexidade Computacional – p. 158
Funções den
5n2 − 9n 4n + 8 ⌊n/3⌋ + 4 2√
n + 7
2n−3 lg n (= log2 n)
Qual é maior: n2 − 9 ou 4n + 8?
Depende do valor de n!
Qual cresce mais?
Comparação assintótica , ou seja, para n ENORME.
Complexidade Computacional – p. 158
Funções den
5n2 − 9n 4n + 8 ⌊n/3⌋ + 4 2√
n + 7
2n−3 lg n (= log2 n)
Qual é maior: n2 − 9 ou 4n + 8?
Depende do valor de n!
Qual cresce mais?
Comparação assintótica , ou seja, para n ENORME.
lg n 2√
n + 7 ⌊n/3⌋ + 4 4n + 8 5n2 − 9n
2n−3
Complexidade Computacional – p. 158
NotaçãoO
Intuitivamente. . .
O(f(n)) ≈ funções que não crescem maisrápido que f(n)
≈ funções menores ou iguais aum múltiplo de f(n)
n2 (3/2)n2 9999n2 n2/1000 etc.
crescem todas com a mesma velocidade
Complexidade Computacional – p. 159
NotaçãoO
Intuitivamente. . .
O(f(n)) ≈ funções que não crescem maisrápido que f(n)
≈ funções menores ou iguais aum múltiplo de f(n)
n2 (3/2)n2 9999n2 n2/1000 etc.
crescem todas com a mesma velocidade
n2 + 99n é O(n2)
33n2 é O(n2)
9n + 2 é O(n2)
0,00001n3 − 200n2 não é O(n2)Complexidade Computacional – p. 159
DefiniçãoSejam T (n) e f(n) funções dos inteiros nos reais positivos.Dizemos que T (n) é O(f(n)) se existem constantespositivas c e n0 tais que
T (n) ≤ c f(n)
para todo n ≥ n0.
tamanho da entrada
cons
umo
dete
mpo
c f(n)
T (n)
n0Complexidade Computacional – p. 160
Mais informalT (n) é O(f(n)) se existe c > 0 tal que
T (n) ≤ c f(n)
para todo n suficientemente GRANDE.
tamanho da entrada
cons
umo
dete
mpo
c f(n)
T (n)
n0
Complexidade Computacional – p. 161
ExemplosT (n) é O(f(n)) lê-se “T (n) é O de f(n)” ou
“T (n) é da ordem de f(n)”
Complexidade Computacional – p. 162
ExemplosT (n) é O(f(n)) lê-se “T (n) é O de f(n)” ou
“T (n) é da ordem de f(n)”
Exemplo 1Se T (n) ≤ 500f(n) para todo n ≥ 10, então T (n) é O(f(n)).
Complexidade Computacional – p. 162
ExemplosT (n) é O(f(n)) lê-se “T (n) é O de f(n)” ou
“T (n) é da ordem de f(n)”
Exemplo 1Se T (n) ≤ 500f(n) para todo n ≥ 10, então T (n) é O(f(n)).Prova: Aplique a definição com c = 500 e n0 = 10.
Complexidade Computacional – p. 162
ExemplosT (n) é O(f(n)) lê-se “T (n) é O de f(n)” ou
“T (n) é da ordem de f(n)”
Exemplo 1Se T (n) ≤ 500f(n) para todo n ≥ 10, então T (n) é O(f(n)).Prova: Aplique a definição com c = 500 e n0 = 10.
Exemplo 210n2 é O(n3).
Complexidade Computacional – p. 162
ExemplosT (n) é O(f(n)) lê-se “T (n) é O de f(n)” ou
“T (n) é da ordem de f(n)”
Exemplo 1Se T (n) ≤ 500f(n) para todo n ≥ 10, então T (n) é O(f(n)).Prova: Aplique a definição com c = 500 e n0 = 10.
Exemplo 210n2 é O(n3).
Prova: Para n ≥ 0, temos que 0 ≤ 10n2 ≤ 10 n3.
Outra prova: Para n ≥ 10, temos 0 ≤ 10n2 ≤ n × n2 = 1 n3.
Complexidade Computacional – p. 162
Mais exemplos
Exemplo 3lg n é O(n).Prova: Para n ≥ 1, tem-se que lg n ≤ 1 n.
Complexidade Computacional – p. 163
Mais exemplos
Exemplo 3lg n é O(n).Prova: Para n ≥ 1, tem-se que lg n ≤ 1 n.
Exemplo 420n3 + 10n log n + 5 é O(n3).
Complexidade Computacional – p. 163
Mais exemplos
Exemplo 3lg n é O(n).Prova: Para n ≥ 1, tem-se que lg n ≤ 1 n.
Exemplo 420n3 + 10n log n + 5 é O(n3).Prova: Para n ≥ 1, tem-se que
20n3 + 10n lg n + 5 ≤ 20n3 + 10n3 + 5n3 = 35 n3.
Outra prova: Para n ≥ 10, tem-se que
20n3+10n lg n+5 ≤ 20n3+n n lg n+n ≤ 20n3+n3+n3 = 22 n3.
Complexidade Computacional – p. 163
Mais exemplos aindaExemplo 53 lg n + lg lg n é O(lg n).Prova: Para n ≥ 2, tem-se que
3 lg n + lg lg n ≤ 3 lg n + lg n = 4 lg n.
[Note que lg lg n não é definida para n = 1.]
Complexidade Computacional – p. 164
Mais exemplos aindaExemplo 53 lg n + lg lg n é O(lg n).Prova: Para n ≥ 2, tem-se que
3 lg n + lg lg n ≤ 3 lg n + lg n = 4 lg n.
[Note que lg lg n não é definida para n = 1.]
Exemplo 610100 é O(1).
Complexidade Computacional – p. 164
Mais exemplos aindaExemplo 53 lg n + lg lg n é O(lg n).Prova: Para n ≥ 2, tem-se que
3 lg n + lg lg n ≤ 3 lg n + lg n = 4 lg n.
[Note que lg lg n não é definida para n = 1.]
Exemplo 610100 é O(1).Prova: Para n ≥ 1, tem-se que
10100 = 10100 n0 = 10100 × 1.
[Note que n não precisa aparecer, já que estamos lidando
com funções constantes.]
Complexidade Computacional – p. 164
Uso da notaçãoOO(f(n)) = {T (n) : existem c e n0 tq T (n) ≤ cf(n), n ≥ n0}
“T (n) é O(f(n))” deve ser entendido como “T (n) ∈ O(f(n))”.
“T (n) = O(f(n))” deve ser entendido como “T (n) ∈ O(f(n))”.
“T (n) ≤ O(f(n))” é feio.
“T (n) ≥ O(f(n))” não faz sentido!
“T (n) é g(n) + O(f(n))” significa que existe constantespositivas c e n0 tais que
T (n) ≤ g(n) + c f(n)
para todo n ≥ n0.
Complexidade Computacional – p. 165
Nomes de classesO
classe nome
O(1) constante
O(lg n) logarítmica
O(n) linear
O(n lg n) n log n
O(n2) quadrática
O(n3) cúbica
O(nk) com k >= 1 polinomial
O(2n) exponencial
O(an) com a > 1 exponencial
Complexidade Computacional – p. 166
ExercíciosExercício 2.AProve que n2 + 10n + 20 = O(n2)
Exercício 2.BProve que 300 = O(1)
Exercício 2.CProve que ⌈n/3⌉ = O(n)
É verdade que n = O(⌊n/3⌋)?
Exercício 2.DProve que lg n = O(log
10n)
Exercício 2.EProve que n = O(2n)
Exercício 2.FProve que lg n = O(n)
Exercício 2.GProve que n/1000 não é O(1)
Exercício 2.HProve que 1
2n2 não é O(n)
Complexidade Computacional – p. 167
Mais exercíciosExercício 2.ISuponha T definida para n = 0, 1, . . .
Se T (n) = O(1), mostre que existe c′ tal que T (n) ≤ c′ para todo n ≥ 0.Se T (n) = O(n), mostre que existe c′ tal que T (n) ≤ c′n para todo n ≥ 1.
Exercício 2.JProve que n2 + 999n + 9999 = O(n2).
Exercício 2.KProve que 1
2n(n + 1) = O(n2).
Exercício 2.LÉ verdade que 1
100n2 − 999n − 9999 = O(n)? Justifique.
Exercício 2.MSuponha que f(n) = n2 quando n é par e f(n) = n3 quando n é ímpar.É verdade que f(n) = O(n2)?É verdade que f(n) = O(n3)?É verdade que n2 = O(f(n))?É verdade que n3 = O(f(n))?
Complexidade Computacional – p. 168
Mais exercícios ainda
Exercício 2.NÉ verdade que n2 = O(2n)?
Exercício 2.OÉ verdade que lg n = O(
√n)?
Exercício 2.PSuponha f(n) = 64n lg n e g(n) = 8n2, com n inteiro positivo.Para que valores de n temos f(n) ≤ g(n)?
Exercício 2.Q (bom!)Suponha T e f definidas para n = 1, 2, . . . Mostre que se T (n) = O(f(n)) e f(n) > 0 paran ≥ 1 então existe c′ tal que T (n) ≤ c′f(n) para todo n ≥ 1.
Exercício 2.R (bom!)Faz sentido dizer “T (n) = O(n2) para n ≥ 3”?
Complexidade Computacional – p. 169
Mais exercícios ainda aindaExercício 2.SÉ verdade que 2n = O(n)?É verdade que n = O(lg n)?Justifique.
Exercício 2.TÉ verdade que n +
√n é O(n)?
É verdade que n é O(√
n)?É verdade que n2/3 é O(
√n)?
É verdade que√
n + 1000 é O(n)?
Exercício 2.UÉ verdade que lg n = O(n1/2)?É verdade que
√n = O(lg n)?
É verdade que lg n = O(n1/3)?Justifique. (Sugestão: prove, por indução, que lg x ≤ x para todo número real x ≥ 1.)
Exercício 2.VÉ verdade que ⌈lg n⌉ = O(lg n)?
Complexidade Computacional – p. 170
MT multifita por MT fita únicaDuas máquinas são equivalentes se elas reconhecem amesma linguagem.
Teorema . Dada uma máquina de Turing multifitaM , podemos construir uma uma máquina de Turing
S com uma única fita e equivalente a M . Alémdisso, se tendo como entrada uma cadeia de
comprimento n a máquina M faz não mais do quet(n) ≥ n passos, então S faz O(t2(n)) passos.
Prova: Digamos que M tenha k fitas. Já vimos comoconverter M para S.
Complexidade Computacional – p. 172
Suponha
M = (Q, Σ, Γ, δ, q1, qaceitação, qrejeição)
S = (Q′, Σ′, Γ′, δ′, q′1, q′
aceitação, q′rejeição)
Γ′ = Γ∪•
Γ
•
Γ = {•γ: γ ∈ Γ}
Se M faz não mais do que t(n) passos, então ocomprimento de cada cadeia em uma fita de M é ≤ t(n).
Logo, o maior comprimento da cadeia na fita de S ék + 1 + kt(n) = k(t(n) + 1) + 1.
Complexidade Computacional – p. 173
Inicialização
S = Com entrada w = w1w2 · · ·wn Acerte a fita de S para
representar todas as k fitas de M :
#•
w1 w2 · · ·wn#•
⊔ #•
⊔ # · · ·#
O número de passos para inicialização é igual ao númerode passos para
inserir o primeiro # e deslocar w e outro #;
inserir k−1 cópias de “•
⊔ #”;
voltar a cabeça da fita para primeira posição.
Logo, esse número de passos é = (2(1 + n + 1 + 2(k − 1))).
Complexidade Computacional – p. 174
Esquerda para a direita
A cadeia de S é varrida da esquerda para a direitaguardando
o estado presente da máquina M ; e
os k símbolos que estão sob as cabeças de M .
Para isto podemos ter estados
Q × Γi com i = 0, 1, . . . , k.
O número de passos necessários para isto é
≤ k(t(n) + 1) + 1.
Complexidade Computacional – p. 175
Configurações deS
{q}# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . .•
γk . . . #
# . . .•
γ1 {q, γ1} . . . # . . .•
γ2 . . . # . . . # . . .•
γk . . . #
# . . .•
γ1 . . . # . . .•
γ2 {q, γ1, γ2} . . . # . . . # . . .•
γk . . . #
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . .•
γk {q, γ1, . . . , γk}#
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . .•
γk . . . #{q, γ1, . . . , γk}
Complexidade Computacional – p. 176
Direita para a esquerda
Baseada no estado {q, γ1, . . . , γk} a máquina S percorre acadeia na sua fita da esquerda para a direita parando emcada símbolo
•
γi, realizando as transições da máquina M :
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . . σ•
γi α . . . # . . . # . . .•
γk . . . #
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . .•
σ γiα . . . # . . . # . . .•
σk . . . #
seδ(q, γ1, . . . , γi, . . . , γk) = δ(p, . . . , σ, . . . , L, . . .)
Se não houver “complicação” o número de passosnecessários para isto é
≤ k(t(n) + 1) + 1 + 2k.
Complexidade Computacional – p. 177
Complicação
•
γi pode estar imediatamente antes de um # e M devemover a cabeça da i-ésima fita para a direita:
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . . σ•
γi # . . . # . . .•
γk . . . #
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . . α•
# . . . # . . .•
σk . . . #
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . . α•
⊔•
# . . . # . . .•
σk . . . #
# . . .•
γ1 . . . # . . .•
γ2 . . . # . . . # . . . α•
⊔ # . . . # . . .•
σk . . . #
Neste caso precisamos deslocar vários símbolos para adireita. Número de passos necessários para cada fita de Mé ≤ 2(k(t(n) + 1) + 1).
Total: ≤ 2k(k(t(n) + 1) + 1)
Complexidade Computacional – p. 178
Número de passos deS
A simulação continua até que M pare.
Inicialização: ≤ (2(1 + n + 1 + 2(k − 1))) = O(n)
Cada passo de M :
Esquerda para a direita: ≤ k(t(n) + 1) + 1 = O(t(n))
Direita para a esquerda: ≤ 2k(k(t(n) + 1) + 1) = O(t(n))
Número de passos de M ≤ t(n)
Logo, número de passos de S é O(n + t2(n))
Como t(n) ≥ n, a simulação toda pode ser realizada emO(t2(n)) passos
Complexidade Computacional – p. 179