O que significa indecidível?

//

t0tgb

Perguntado por: Herr Gottlieb Weis B.Sc. | Última atualização: 15 de junho de 2021

Classificação por estrelas: 4,4/5 (classificações de 74 estrelas)

Na ciência da computação teórica, uma propriedade é chamada decidível (também recursivamente, recursivamente derivável) em um conjunto se houver um procedimento de decisão para ela. … Se não houver “não” tal procedimento de decisão, então a propriedade é chamada indecidível.

Quando um conjunto é decidível?

Definição Um conjunto M ⊆ Σ∗ é dito decidível se e somente se a função característica χM : Σ∗ → {0,1} é computável. Teorema Um conjunto M é decidível se e somente se existe uma TM A com L(A) = M e tal que A para em cada entrada.

O que são perguntas decidíveis?

Para Heinz von Foerster, essas questões eram consideradas questões fundamentalmente decidíveis. As respostas a essas perguntas já foram decididas e são conhecidas – por exemplo, por meio de teorias, regulamentos ou leis. Os responsáveis ​​por essas respostas e suas consequências são seus autores, inventores, legisladores, etc.

O que significa semidecidível?

Léxico da matemática semi-decidível

Um conjunto A é semi-decidível se for o domínio de uma função computável. Isso significa que existe um algoritmo que para exatamente nas entradas de A.

O problema da parada é semidecidível?

Embora isso possa ser facilmente respondido para muitos algoritmos, o matemático Alan Turing conseguiu provar que não há algoritmo que responda a essa pergunta para todos os algoritmos possíveis e quaisquer entradas. … O problema da parada não é, portanto, algoritmicamente decidível.

Decidível, indecidível, semidecidível?

16 perguntas relacionadas encontradas

Quando uma máquina de Turing para?

Uma transição de estado para o estado 0 e o caractere b não é definida na tabela de Turing. Isso faz com que a máquina de Turing pare quando estiver no estado 0 lendo o caractere b. Como o estado 0 não é o estado final, ele rejeita a palavra de entrada neste caso.

Toda linguagem é semidecidível?

(Use que uma máquina de Turing de 2 fitas pode ser simulada por uma máquina de Turing de 1 fita). (Use que uma máquina de Turing de 2 fitas pode ser simulada por uma máquina de Turing de 1 fita). Toda linguagem decidível é semidecidível.

O problema da parada é recursivo?

Um dos problemas mais importantes, que é recursivamente enumerável, mas não recursivamente, é o chamado problema da parada. : o conjunto de codificações de todas aquelas máquinas de Turing que não aderem à sua própria codificação como entrada.

A classe de linguagens recursivamente enumeráveis ​​está fechada abaixo da média?

Em quais propriedades teóricas de conjuntos diferem as linguagens recursivas e as linguagens recursivamente enumeráveis? As linguagens recursivas são fechadas sob formação de complemento, as recursivamente enumeráveis ​​não (cf. ponto 8). Cada uma das duas classes de linguagem é fechada sob interseção e união.

Qual é o problema de decisão?

Um problema de decisão é a questão de se e como um procedimento de decisão pode ser formulado para uma dada propriedade.

Todas as linguagens são decidíveis?

Provas. Nos exercícios mostra-se que para toda gramática G a linguagem L(G) é decidível.

Quando uma linguagem formal é decidível?

Ou seja, uma linguagem A é dita decidível se existe uma máquina de Turing M com A = L(M) que para a cada entrada, onde L(M) é a linguagem aceita pela TM M. Toda linguagem decidível também é recursivamente enumerável, ou seja, se uma linguagem não é recursivamente enumerável, então ela também não é decidível.

O conjunto de números primos é recursivamente enumerável?

Vamos começar com os conjuntos recursivamente enumeráveis. Um conjunto recursivamente enumerável de números naturais nada mais é do que um (possivelmente … Esses conjuntos também são chamados recursivos, solúveis, computáveis ​​ou decidíveis. Um exemplo de tal conjunto é o conjunto de todos os números primos.

Se uma linguagem L é decidível, então todo subconjunto de L também é decidível?

Para toda linguagem L recursivamente enumerável, L = Σ∗ − L. A propriedade de ser um subconjunto de Σ∗ vale para todas as linguagens recursivamente enumeráveis ​​(assim como seu complemento), portanto é uma propriedade trivial. … d) Se L é decidível, então todo subconjunto de L é decidível.

Por que devem existir línguas para as quais o problema da palavra é indecidível?

O problema de palavras para linguagens do tipo 1 é decidível. O tempo necessário é no máximo exponencial, a complexidade do espaço é exatamente linear. Em particular, o problema de palavras também pode ser decidido para classes de idiomas ainda mais restritas.

Um subconjunto de um conjunto recursivamente enumerável é sempre recursivamente enumerável?

Todo conjunto finito é recursivamente enumerável. Todo conjunto recursivamente enumerável é enumerável, mas nem todos os conjuntos enumeráveis ​​são recursivamente enumeráveis. Todo conjunto infinito recursivamente enumerável tem subconjuntos que não são recursivamente enumeráveis.

A linguagem vazia é decidível?

A decidibilidade do problema do vazio depende da complexidade da gramática subjacente: para gramáticas do tipo 2 ou superior na hierarquia de Chomsky, o problema do vazio é decidível, mas para gramáticas até o tipo 1 em geral não é.

Como você chama uma máquina de turing que mantém todas as entradas no estado de aceitação ou rejeição?

Na ciência da computação teórica, uma máquina de Turing alternada (ATM) é uma máquina de Turing não determinística que estende as regras usuais para aceitar uma entrada. Os estados da máquina são divididos em estados existenciais e universais.

As máquinas de Turing são determinísticas?

Uma máquina de Turing determinística (daqui em diante DTM) tem uma função de transição que, dado um estado e um símbolo sob o cabeçote de leitura, especifica três coisas: o símbolo a ser escrito na fita, a direção na qual o cabeçote de leitura deve ser movido e o estado para o qual mudou…

Deja un comentario