3 ms·
Remember that TM’s read their input left to right. Therefore if there is some fixed number N where the TM halts on all length N inputs, then it would halt in th
by LPisGood 1y ago
Remember that TM’s read their input left to right. Therefore if there is some fixed number N where the TM halts on all length N inputs, then it would halt in the same number of steps if input where length N+1 because TM halts before it can read the additional input.