O termo "continuidade" tem um significado diferente em matemática e em CS?

Question

Faço essa pergunta por causa de algumas declarações em questão "O que é a 'continuidade' como um termo em computável análise?" fazendo-me desconfiado.

Eu sou engenheiro, não cientista da computação, então eu não tenho a máquina de Turing, mas portas lógicas em mente quando estou a pensar algébrico operações realizadas com os dispositivos.

Eu li a resposta para a pergunta "Por que são computáveis funções contínuas?" e entendida da seguinte forma:

Porque o dispositivo de entrada é de comprimento infinito (um número decimal com um número infinito de dígitos após o ponto decimal), o dispositivo (e.g.Máquina de Turing ou computador) não é possível ler o número inteiro antes de escrever o $n$-ésimo dígito de saída.

Em vez disso, o dispositivo só pode ter lido $m(n)$ dígitos de entrada quando ele escreve o $n$-ésimo dígito de saída.

Se o primeiro $n$ dígitos de saída de alguns função depende apenas do primeiro $m(n)$ dígitos de entrada, a função é contínua.

No entanto, se eu entender esta argumentação corretamente, a palavra "contínuo" em computação teoria não é idêntica à palavra "contínuo" em matemática:

Arredondamento em direção a zero apenas exigem a leitura da entrada até o ponto decimal (de modo $m(n)= ext{const.}$);no entanto, a função matemática a ser calculado não é um "contínuo" de acordo com a definição matemática do termo.

Podemos também executar um dígito-sábio operação ($m(n)=n$ e certos dígitos após o ponto decimal;por exemplo, substitua todas as 4s por 9s e todos os 9s por 4s.Tanto quanto eu entendo, a função a ser calculado não é contínua em qualquer intervalo de $\mathbb{R}$ (no entanto, seria clique com o botão direito contínua em $[0,\infty)$ e deixou-contínua no $(-\infty,0]$).

E se eu não fazer um erro conceitual e usamos uma equilibrado sistema de numeração (como um Russo computador na década de 1960) em vez de o sistema decimal, um algoritmo semelhante (troca de 0s e 1s em vez de 4s e 9s) poderia representar uma função matemática que é não mesmo direcional contínua em qualquer intervalo de $\mathbb{R}$.

Perguntas:

O computability dependem do sistema de numeração a ser utilizada (como o exemplo com o balanced sistema de numeração sugere) ou é o termo "computável" mesmo supondo que um determinado sistema de numeração a ser utilizada?

É a observação correta, que o termo "contínuo" não tem o mesmo significado em matemática e CS?

Answer 1

Se fôssemos usar a expansão decimal para representar números reais, o seu raciocínio é o trabalho.Mas que nos dá muito mal comportado noção de computability:

Proposição:A multiplicação por 3 não é computável em relação à representação decimal.

Prova:Suponha que a entrada começa 0.3333333...Em algum ponto, o nosso computação precisa para começar a produzir algo.As melhores opções são 0.e 1..No primeiro caso, temos asneira, se a nossa entrada tem um 4 como próximo dígito nós não tinha olhado;no segundo caso, a 2 nos faz mal.Assim, nós não podemos saída garantida prefixo da solução.

Usando uma base diferente produziria uma noção diferente de computability, mas nenhum deles é adequado.Algumas maneiras em que toda a produção da mesma boa noção de computability são:

1. O código de um real $x$ como uma seqüência de rationals $(q_n)_{n \in \mathbb{N}}$ de tal forma que $|x - q_n| < 2^{-n}$.
2. O código de um real através de uma assinado representação dígito, usando $\{-1,0,1\}$.
3. O código de um real $x$ como uma seqüência de intervalos de racionais $(I_n)_{n \in \mathbb{N}}$ com $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

Quando falamos sobre computability de uma função sobre as reais sem especificar que tipo de representação que estamos usando, queremos dizer um desses (ou outro equivalente).Isto é, assim como nós, não sempre usando a topologia Euclidiana em reais, se nós, que é apenas o caso padrão.Podemos agora afirmar:

Teorema:A utilização de funções reais que são computáveis (wrt o padrão de representação) em relação à oracle algumas são exatamente as funções contínuas (wrt a topologia Euclidiana).

Voltando ao arredondamento, isso mostra que é perfeitamente exata de arredondamento não pode trabalhar.No entanto, podemos circumvene isso, não restringindo-nos às funções.Por exemplo, a tarefa seguinte é computável:

Dado um número real $x \in [0,1]$, saída $0$ ou $1$.Se $x < 0.501$, e , em seguida, $0$ é uma solução aceitável e se $x > 0.499$, e , em seguida, $1$ é uma solução aceitável.

Se a entrada para a tarefa acima é de $[0.499,0.501]$, e , em seguida, a resposta que temos não depende apenas do real que estamos olhando, mas em determinado código para que o real que o nosso algoritmo lê.Que pode fazer o raciocínio sobre algoritmos ligeiramente mais complicado, mas nós realmente não pode evitar isso.