How to calculate the characteristic Function with a Turning-Machine?

Asked Oct 18 '21 at 14:13

Active Oct 18 '21 at 14:13

Viewed 117 times

I have the following question that I need to answer :

Proof that the set $P=\{w \in \{0,1\}^{*}|w \ is \ divisible \ by \ 2\}$ is decidable. Construct a Turing-Machine which calculates the characteristic Function of $P$.

It is very obvious to me how to construct the Turning Machine. I construct a loop which goes to the end and if there is a one it is not divisible and if it is a zero then it is. But the problem now is how to output my answer. Do I simply delete every number on the tape and write then a zero or a one. Or do I define a state and say if it ends in $q_4$ it is even and if it is in $q_5$ it is odd?

asked Oct 18 '21 at 14:13

Iwan5050

1

Turning machine? – Paul Frost Oct 18 '21 at 14:19
Not exactly clear what $w$ is, I guess a binary string from which we want to know whether it represents an even number. Just determine the last digit of this string and verify whether it is $0$. – Peter Oct 18 '21 at 14:20
Yes but how do I output wether it is 0 or not? – Iwan5050 Oct 18 '21 at 14:25
Just write the digit behind the input with one space between. – Peter Oct 18 '21 at 14:40
OK ty this is what I wanted to know – Iwan5050 Oct 18 '21 at 14:53

How to calculate the characteristic Function with a Turning-Machine?

0 Answers0