ماشین مبدل دودویی یک عدد دودویی با $n$ رقم را از ورودی می‌گیردو با فشار دادن یکی از دو دکمه‌ی آن، یکی از دو تبدیل زیر را روی عدد ورودی انجام می‌دهد.

1. دکمه‌ی یک: سمت راست ترین رقم را از 0 به 1 و از 1 به 0 تغییر می‌دهد.

2. دکمه دو: سمت راست ترین رقم 1 را پیدا می‌کند و رقم سمت چپ آن را از 0 به 1 و از 1 به 0 تغییر می‌دهد. دقت کنید در صورتی که سمت راست ترین 1 در سمت چپ ترین مکان باشد یا رشته تمام 0 باشد، تغییری انجام نمی دهد.

برای مثال با استفاده از ماشین مبدل دودویی می‌توان عدد 001001 را به 011001 تبدیل کرد. روش تبدیل به این صورت است که ابتدا دکمه‌یک ، سپس دکمه دو و در انتها دکمه‌یک را فشار می‌دهیم. ثابت کنید با استفاده از ماشین مبدل دودویی می‌توان هر عدد دودویی با $n$رقم را به هر عدد دودویی با $n$ رقم تبدیل کرد.