Écart entre

Si est l'ensemble des temps d'arrêt des machines de Turing à états sur un alphabet binaire avec une bande initiale vide, alors . $HT(n)$ $n$ $BB(n) = \max HT(n)$

Que dire du deuxième plus grand nombre de ? Appelez cela . $HT(n)$ $BB_2(n)$

est trivialement non calculable, car il permet de calculer : il suffit d'attendre qu'une autre machine s'arrête. Naïvement, je m'attendrais à ce que l'écart soit "comme un castor occupé", augmentant plus rapidement que n'importe quelle fonction calculable. Est-ce prouvable? $BB_2(n)$ $BB(n)$ $BB(n) - BB_2(n)$

computability Geoffrey Irving
la source

Supposons que l'un des n états ne soit pas accessible.

micro

@mic: Je ne pense pas que ce soit pertinent.

semble hautement improbable.

B B (n - 1) = B B_{2} (n)

$BB(n-1) = BB_2(n)$

Geoffrey Irving

Cela dépendra de l'encodage. Si vous inversez les états d'acceptation / de rejet, le nombre d'états reste le même, tout comme le temps d'arrêt, ce qui ferait

B B (n) = B B_{2} (n)

$BB(n)=BB_2(n)$

Lance Fortnow

C'est pourquoi je laisse

l' ensemble des temps d'arrêt, de sorte que l'écart est non nul par construction.

H T (n)

$HT(n)$

Geoffrey Irving

Est-il même possible de prouver que l'écart n'est finalement pas de 1?

Geoffrey Irving

Le nombre d'états est juste une notion de complexité de la description des fonctions calculables dans un modèle, vous pouvez choisir n'importe quel modèle de calcul et tout encodage d'entre eux sous forme de chaînes binaires, puis prendre la longueur n et définir BB (n) en fonction de cela et tous les résultats intéressants sur BB (n) seraient toujours vrais, il y a une particularité ennuyeuse sur le modèle TM et le nombre d'états.
Rien ne les empêche de choisir un modèle modifié de MT. Généralement, les questions qui ne sont pas invariables sous de tels changements de représentation des MT ne concernent pas la calculabilité ou les MT mais la représentation particulière (comme BB (n) mod 2, etc.) et à moins qu'il y ait une raison particulière pour qu'elles soient intéressantes, elles ne ça vaut pas la peine de poursuivre à mon humble avis. Ce sont de jolis puzzles mais sans grande valeur. l Notez que "BB (n) n'est pas calculable" est invariant en cas de changement de représentation des MT.
Cette question est-elle donc invariante sous le changement de représentation des fonctions calculables? Je pense que la réponse est non.

je. Considérons une représentation où nous avons deux états spéciaux 0 et 1 et où 0 est initial et peut simplement passer à 1 ou 0 est inaccessible et 1 est initial. Dans ce codage, la différence est de 1.

ii. Considérons une autre représentation où nous avons un UTM plus une partie qui écrit n bits sur bande avant de passer à UTM. Ainsi, la question devient max f (x) - 2ndmax f (x) où les maximales sont sur des chaînes de n bits et où f est une fonction arbitraire calculable. Nous avons seulement besoin de trouver une fonction calculable là où elle n'est pas calculable. Je n'y ai pas beaucoup réfléchi mais mon instinct dit qu'il existe une telle fonction calculable.

Kaveh
la source

Rien de tout cela n'est pertinent, car j'ai choisi les machines de Turing standard comme ma notion de calcul. Je suis d'accord qu'il existe quelques définitions communes différentes (bande un ou deux côtés, que la bande commence par zéro ou un symbole vide spécial), mais rien de tel que les UTM préencodées que vous mentionnez.

Geoffrey Irving

n

$n$

Permettez-moi de l'exprimer différemment: pourquoi êtes-vous intéressé par la réponse? C'est une belle énigme comme beaucoup d'autres sur BB pour une représentation particulière des MT, mais elles ne révèlent rien sur la calculabilité et le calcul. Le choix de la norme pour la représentation de la MT était une action arbitraire, on aurait pu choisir ma première représentation ci-dessus et la réponse à votre question aurait été 1. Tout simplement parce qu'elle est appelée standard ne la rend pas spéciale parmi les représentations.

Kaveh

Ce n'est pas différent de demander si une équation diophantienne E choisie arbitrairement a une solution entière. Il existe une infinité de telles équations, sans raison pour laquelle on s'intéresse à E ce n'est pas une question très intéressante. Lorsque les gens posent des questions comme "calculabilité de BB (n) mod 2", ils pensent poser des questions profondes sur la calculabilité alors qu'en réalité, cela ressemble plus à demander la solubilité d'une équation diophantienne choisie arbitrairement, c'est juste pour certains l'oeil.

Kaveh

Je suis intéressé parce que je crois que la réponse est la même pour tous les encodages non-déférés: c'est indémontrable, c'est indémontrable que c'est indémontrable, etc. Mais je ne sais pas comment formuler cela, alors j'en ai choisi un. Le fait qu'il soit trivial pour des encodages spécialement choisis est similaire au problème d'arrêt pouvant être résolu pour les machines d'arrêt par construction.

Geoffrey Irving

Écart entre

Réponses: