Distância entre

13

Se é o conjunto de tempos de parada de máquinas de Turing state em um alfabeto binário com fita inicial vazia, então .HT(n)nBB(n)=maxHT(n)

O que podemos dizer sobre o segundo maior número em HT(n) ? Chame isso de BB2(n) .

BB2(n) é trivialmente incontestável, pois permite calcular BB(n) : basta aguardar mais uma máquina parar. Ingenuamente, eu esperaria que o intervalo BB(n)−BB2(n) seja "ocupado como um castor", crescendo mais rápido do que qualquer função computável. Isso é comprovável?

computability Geoffrey Irving
fonte
Suponha que um dos n estados não esteja acessível.
mic
@mic: Eu não acho que isso seja relevante. BB(n-1)=BB2(n) parece altamente improvável.
Geoffrey Irving
1
Isso vai depender da codificação. Se você inverter os estados de aceitação / rejeição, o número de estados permanecerá o mesmo e também será o tempo de interrupção, o que tornaria BB(n)=BB2(n) .
Lance Fortnow
6
É por isso que deixei HT(n) ser o conjunto de tempos de parada, para que a diferença seja diferente de zero por construção.
Geoffrey Irving
1
É possível provar que a diferença não é 1?
Geoffrey Irving

Respostas:

-1

  1. O número de estados é apenas uma noção de complexidade da descrição de funções computáveis ​​em um modelo; você pode escolher qualquer modelo de computação e qualquer codificação deles como cadeias binárias e, em seguida, assumir o comprimento como ne definir BB (n) com base em que e todos os resultados interessantes sobre o BB (n) ainda sejam verdadeiros, há um especial chato sobre o modelo de MT e o número de estados.

  2. Não há nada que os impeça de escolher qualquer modelo modificado de TMs. Geralmente, as perguntas que não são invariantes sob essas mudanças de representação de TMs não são sobre computabilidade ou MTs, mas sobre a representação específica (como BB (n) mod 2, etc.) e, a menos que haja alguma razão específica para serem interessantes, elas não vale a pena perseguir imho. Eles são bons quebra-cabeças, mas não têm muito valor. l Observe que "BB (n) não é computável" é invariável sob a mudança de representações de TMs.

  3. Então, essa pergunta é invariável sob a mudança de representação de funções computáveis? A resposta que eu acho é não.

Eu. Considere uma representação em que temos dois estados especiais 0 e 1 e 0 é inicial e apenas pode fazer a transição para 1 ou 0 é inacessível e 1 é inicial. Nesta codificação, a diferença é 1.

ii. Considere outra representação em que temos um UTM mais uma parte que grava n bits na fita antes de fazer a transição para o UTM. Portanto, a questão se torna max f (x) - 2ndmax f (x) onde máximos estão acima de n bits e onde f é uma função computável arbitrária. Só precisamos encontrar uma função computável onde isso não é computável. Eu não pensei muito sobre isso, mas meu intestino diz que existe uma função tão computável.

Kaveh
fonte
2
Nada disso é relevante, porque escolhi as máquinas de Turing padrão como minha noção de computação. Concordo que existem algumas definições comuns diferentes (fita de um ou dois lados, se a fita começa com zero ou algum símbolo vazio especial), mas nada como os UTMs pré-codificados que você menciona.
Geoffrey Irving
1
Usar para contar uma codificação totalmente diferente seria uma pergunta diferente e muito menos interessante, pois, como você diz, a codificação pode ser escolhida para quebrar a questão. n
Geoffrey Irving
Deixe-me colocar de uma maneira diferente: por que você está interessado na resposta? É um bom quebra-cabeças, como muitos outros sobre o BB, para uma representação específica de TMs, mas eles não revelam nada sobre computabilidade e computação. A escolha do padrão para representação da TM foi uma ação arbitrária; alguém poderia ter escolhido minha primeira representação acima e a resposta à sua pergunta seria 1. Só porque é chamado de padrão não o torna especial entre representações.
Kaveh
Isso não é diferente de perguntar se alguma equação de Diophantienne E escolhida arbitrariamente tem uma solução inteira. Existem infinitas equações desse tipo, sem uma razão para se interessar por E, não é uma pergunta muito interessante. Quando as pessoas fazem perguntas como "computabilidade do BB (n) mod 2", pensam que estão fazendo perguntas profundas sobre computação, enquanto na realidade é mais como pedir solubilidade de alguma equação de Diofantiana escolhida arbitrariamente, é apenas algumas delas que parecem mais agradáveis. o olho.
Kaveh
2
Estou interessado porque acredito que a resposta é a mesma para todas as codificações não -egeradas: é improvável, é improvável que seja improvável, etc. Mas como não sei como expressar isso, escolhi uma. O fato de ser trivial para codificações especialmente escolhidas é semelhante ao problema de parada ser solucionável para máquinas de parada por construção.
Geoffrey Irving