Embed Size (px)
Citation preview
Maacutequinas de Turing e outros modelos
Yuri Tavares dos Passos
Maacutequinas de vaacuterias pilhas
Maacutequina de pilha ou autocircmato de pilha eacute dado por M = (QΣГδq0Z0F)
ndash Q eacute o conjunto de estados
ndash Σ siacutembolos de fita
ndash Г siacutembolos de pilha
ndash δ Q x Σ ⋃ ε x Г rarr 2Σ x Г
Exemplo δ(qaX) = (pYZ) (rε) Na fita ε eacute usado para natildeo avanccedilar a fita Na pilha ε indica que o topo foi apagado
Maacutequinas de vaacuterias pilhas
ndash q0 estado inicial
ndash Z0 siacutembolo que indica fim da pilha
ndash FsubeQ conjunto de estados de aceitaccedilatildeo
Maacutequinas de vaacuterias pilhas
Maacutequinas de vaacuterias pilhas
A maacutequina de vaacuterias pilhas eacute uma extensatildeo deste autocircmato para usar mais de uma pilha
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
Maacutequina de pilha ou autocircmato de pilha eacute dado por M = (QΣГδq0Z0F)
ndash Q eacute o conjunto de estados
ndash Σ siacutembolos de fita
ndash Г siacutembolos de pilha
ndash δ Q x Σ ⋃ ε x Г rarr 2Σ x Г
Exemplo δ(qaX) = (pYZ) (rε) Na fita ε eacute usado para natildeo avanccedilar a fita Na pilha ε indica que o topo foi apagado
Maacutequinas de vaacuterias pilhas
ndash q0 estado inicial
ndash Z0 siacutembolo que indica fim da pilha
ndash FsubeQ conjunto de estados de aceitaccedilatildeo
Maacutequinas de vaacuterias pilhas
Maacutequinas de vaacuterias pilhas
A maacutequina de vaacuterias pilhas eacute uma extensatildeo deste autocircmato para usar mais de uma pilha
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
ndash q0 estado inicial
ndash Z0 siacutembolo que indica fim da pilha
ndash FsubeQ conjunto de estados de aceitaccedilatildeo
Maacutequinas de vaacuterias pilhas
Maacutequinas de vaacuterias pilhas
A maacutequina de vaacuterias pilhas eacute uma extensatildeo deste autocircmato para usar mais de uma pilha
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
Maacutequinas de vaacuterias pilhas
A maacutequina de vaacuterias pilhas eacute uma extensatildeo deste autocircmato para usar mais de uma pilha
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
A maacutequina de vaacuterias pilhas eacute uma extensatildeo deste autocircmato para usar mais de uma pilha
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequinas com duas pilhas
Provandash Se uma linguagem eacute RE entatildeo existe uma MT
que a aceite
ndash Esta MT Pode ser simulada por um autocircmato de duas pilhas da seguinte forma
Quebre a fita da MT em duas partes a partir da cabeccedila de leitura
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
Na Maacutequina de Pilhas faccedila a pilha esquerda (primeira pilha) conter todos os siacutembolos a esquerda da fita da MT
A pilha direita (segunda pilha) guarda todos os siacutembolos agrave direita da fita da MT
ndash Considere S o nome desta Maacutequina de pilhas
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
ndash S possuiraacute um marcador de fundo de pilha A pilha estaacute vazia quando soacute possui este marcador de fundo de pilha
ndash Suponha que a palavra w$ esteja na entrada de S S copia w no topo de sua primeira pilha
ndash S extrai um simbolo por vez e empilha na pilha esquerda Agora a segunda pilha conteraacute w com o topo na extremidade esquerda de w
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de vaacuterias pilhas
ndash S pode simular a MT caminhando em suas pilhas
ndash O siacutembolo no topo da segunda pilha corresponde ao siacutembolo atual
ndash Se a MT anda para direita este siacutembolo eacute empilhado na primeira pilha e desempilhado da segunda
ndash Se a MT anda para esquerda o primeiro siacutembolo da pilha esquerda eacute empilhado na pilha da direita
Se o fundo de alguma pilha for alcanccedilado S possui um siacutembolo B para marcar o branco da maacutequina de Turing
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
A maacutequina de contador pode ser vista como uma maacutequina de vaacuterias pilhas
Ao inveacutes de pilhas temos contadores inteiros natildeo negativos
Estes contadores podem ser incrementados ou decrementados
Quando um contador alcanccedila 0 natildeo pode decrementar
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Uma MC eacute uma restriccedilatildeo de uma MP Ondendash Soacute existem dois siacutembolos de pilha Z0 e X
ndash Z0 representa o 0
ndash Soacute podemos substituir Z0 por XiZ0 onde i eacute o nuacutemero inteiro natildeo negativo a ser armazenado no contador
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Toda linguagem recursivamente enumeraacutevel eacute aceita por uma maacutequina de contadores (MC) com trecircs contadores
Provandash Suponha que a maacutequina de contador C simula uma maacutequina de
pilhas S
ndash Se S possui r-1 siacutembolos de fita entatildeo podemos representar estes siacutembolos por inteiros de 1 a r-1
ndash A pilha seraacute simulada por um nuacutemero na base r
ndash Suponha que a pilha tenha os siacutembolos X1 X2 hellip Xn (o topo eacute X1)
ndash O nuacutemero Xnrn-1 + hellip + X3r2 + X2r1 + X1 representa o conteuacutedo da pilha
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Г = SXYZ Г = 1234
Maacutequinas de contadores
SXY
Z0
123
Z0
321
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Exemplondash Considere que os siacutembolos da fita sejam 0 1 e 2
ndash Temos que r ndash 1 = 3 A base r seraacute r = 4
ndash Entatildeo modificamos os siacutembolos para 1 a r ndash 1 isto eacute 1 2 e 3
ndash Se a pilha tiver em um dado momento a seguinte configuraccedilatildeo
233 (onde 2 estaacute no topo)
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 341 + 2 = 62
ndash Se a pilha tiver em um dado instante a seguinte configuraccedilatildeo
323
ndash Teremos o seguinte nuacutemero inteiro para representar este conteuacutedo
342 + 241 + 3 = 59
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Dois contadores servem para representar as pilhas
O terceiro contador serve para efetuar contas como dividir por r e multiplicar por rndash Lembre-se que C somente soma e subtrai
Para extrair o siacutembolo X1 da pilha devemos devemos substituir o nuacutemero i por ir descartando o resto O resto eacute o X1
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Para trocar um siacutembolo X por outro Y na pilha fazemos que i seja igual a i ndash (Y ndash X) caso Y gt X e i ndash (X ndash Y) caso X gt Y
Para empilhar X fazemos i se tornar ir + X
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
Toda linguagem RE pode ser representado por uma maacutequina de contador com dois contadores apenas
Provandash Faccedila que os trecircs contadores i j e k sejam
representados por um nuacutemero inteiro somente
ndash Este nuacutemero inteiro seraacute m = 2i3j5k
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Maacutequinas de contadores
ndash Note que m eacute representado por uma multiplicaccedilatildeo de nuacutemeros primos A ordem seraacute mantida
Se escolhessemos 2i3j4k entatildeo o nuacutemero 12 poderia ser representado por i = 0 j = 1 e k = 1 ou i = 2 j = 1 e k = 0 Isto tornaria a representaccedilatildeo ambiacutegua
ndash O segundo contador tem a funccedilatildeo de realizar a multiplicaccedilatildeo e divisatildeo por 2 3 e 5
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Computadores pessoais
Os computadores e MT Satildeo equivalentes quanto a aceitaccedilatildeo de linguagens RE Para provar precisamos mostrar quendash Uma MT pode ser simulada em um PC
ndash Um PC pode ser simulado por uma MT
MT em PCndash Pode ser escrito uma MT em qualquer linguagem de
programaccedilatildeo
ndash Existem diversas simulaccedilotildees em sites da internet
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Computadores pessoais
PC em MT
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Computadores pessoais
PC em MTndash Usa uma MT com vaacuterias fitas
ndash Cada componente principal do PC eacute simulado em cada fita
Registradores Contadores de instruccedilatildeo Endereccedilo de memoacuteria atual Conteuacutedo de um arquivo de entrada Rascunho
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Computadores pessoais
PC em MTndash Cada componente guarda o endereccedilo de
memoacuteria e seu conteuacutedo binaacuterio entre e
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Computadores pessoais
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Comparaccedilatildeo de tempo entre MT e PC O tempo de execuccedilatildeo entre cada um dos
modelos acima deve ser limitado por um polinocircmiondash Limite entre problemas trataacuteveis e intrataacuteveis
A MT que simula um PC pode executar n etapas do PC em O(n3) passos
Como esta MT possui vaacuterias fitas a sua conversatildeo para MT de uma fita levaraacute a uma quantidade de passos de no maacuteximo O(n6)
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Tese de Church-Turing
Toda funccedilatildeo computaacutevel pode ser simulada por uma Maacutequina de Turingndash O que eacute uma funccedilatildeo computaacutevel
ndash E se existir uma maacutequina mais poderosa que a MT
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
Referecircncia
[1] HOPCROFT John E ULLMAN Jeffrey D MOTWANI Rajeev Introduccedilatildeo agrave teoria de autocircmatos linguagens e computaccedilatildeo [Rio de Janeiro] Campus c2003 p 328-352
Imagens da versatildeo em inglecircs
